[LUGOS-PROG] Casovna zahtevnost

[Ivo List]

Ce se ne motim lahko z uporabo "malenkost" bolj zapletenih dreves (red black 
trees, avl trees) dosezes ne glede na podatke zahtevnost dodajanja O(log n) 
in zahtevnost iskanja O(log n) za en podatek.

Ce pa uporabis najbolj "neumna" drevesa pa porabis n v najslabsem primeru za 
dodajanje kot za iskanje.

On Thursday 09 of September 2004 22:41, Gregor Berginc wrote:
> > 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

-- 
Alea iacta est.
	[The die is cast]
		-- Gaius Julius Caesar