[LUGOS-PROG] Casovna zahtevnost

[Andrej (Andy) Brodnik]

On Thu, Sep 09, 2004 at 08:47:48PM +0200, Nejc Skoberne wrote:
> 
> > Nekaj casa je ze preteklo odkar sem poslusal APS, ampak jest bi rekel, da
> > je O(log_2(n)). Ce me spomin ne vara, potem ima iskanje poljubnega
> > elementa dvojiskega drevesa isto zahtevnost. Tisto, kar ti zgornja
> > funkcija naredi je zgolj to, da se ustavi en nivo prej, kar pa za funkcijo
> > O nima pomena. Tudi tista tri preverjanja pred zadnjo vrstico so
> > nepomembna.
> 
> Hm. Najprej hvala. V knjigi ki jo imamo pri predmetu pise, da je
> casovna zahtevnost za vse operacije enaka v najboljsem primeru
> O(log(n)), v najslabsem pa seveda O(n), ce je drevo izrojeno (ce
> recimo elemente dodajas ze urejene).
> 
> V bistvu pa mene bolj zanima kako bi dejansko izracunal to casovno
> zahtevnost? A kdo to zna? :)

Najslabsa moznost je preprosta, ali ne?

Za najboljso se uporabi matematicna indukcija.

LPA