[LUGOS-PROG] Casovna zahtevnost

[polz]

On Thursday 09 September 2004 20:18, gregor.berginc at guest.arnes.si wrote:
> Zivjo
>
> > Kako bi vi izracunali casovno zahtevnost te funkcije? Funkcija torej
> > vrne starsa nekega nodea x, v drevesu s korenom root. Aja, to je
> > binarno iskalno drevo.
>
> Nekaj casa je ze preteklo odkar sem poslusal APS, ampak jest bi rekel, da
> je O(log_2(n)). 
Le, ce je drevo uravnotezeno.

V najslabsem primeru je zahtevnost O(n), tipicna pa naj bi bila okrog 
O(log(n)).