[LUGOS-PROG] Casovna zahtevnost

[Gregor Berginc]

> b) Izberi ustrezne parametre problema in oceni casovno zahtevnost
> funkcije.

Hja. Naceloma je casovna zahtevnost odvisna od stevila podatkov, torej 
od n. Po mojem se kaj vec na izpitu tudi ne pricakuje.

Tako je zelo pomemben podatek o porazdelitvi primerov, saj le ta vpliva 
na strukturo drevesa. Potem je seveda pomemben tudi vrstni red 
dodajanja. Npr. ce drevo gradis iz urejene mnozice po vrsti, potem dobis 
izrojen problem, torej O(n). Ce pa bi drevo gradil tako, da v vsakem 
rekurzivnem klicu za koren izberes srednji element, bi dobil optimalno 
oz. uravnotezeno binarno drevo, torej O(logn).

Ampak, kot receno, po mojem moras ti upostevati zgolj n.

Teoreticno naj bi obstajale neke formule za rekurzivne probleme, ki so 
nam jih metali na tablo pri APS2 (Vilfan), ampak to je pa ze predalec nazaj.

Upam, da ti je kaj pomagalo.

lp,
Grega