[LUGOS-PROG] Casovna zahtevnost

[Dushan Vaupotich]

no.. jaz bi se naceloma strinjal s tem.
dodal pa še bi.. za lazje razumevanje..
stevilo primerjav in premikov, da pregledas dvojisko iskalno drevo (ne
bayerjevo al pa katerokoli drugo), je enako višini drevesa. 
višina polnega drevesa z n podatki je proporcialna log(n)..



-----Original Message-----
From: Gregor Berginc [mailto:gregor.berginc at guest.arnes.si] 
Sent: Thursday, September 09, 2004 10:42 PM
To: lugos-prog at lugos.si
Subject: Re: [LUGOS-PROG] Casovna zahtevnost

> 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