[LUGOS-PROG] Casovna zahtevnost

[Nejc Skoberne]

Zdravo.

> 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? :)

-- 
Nejc Skoberne
E-mail: nejc.skoberne at guest.arnes.si