O(n) ???!!!

[Gost]

Slozenost algoritama

imamo def.da ako su f(n) i g(n) dvije f-je na N ,kazemo da je f(n)=O(g(n)) ako postoji const>=0 t.d. za dov.vel. n ispunjeno f(n)=c g(n)

Kako se odreduje slozenost nekog algoritma??

recimo klasicni sort kaze da ima slozenost O(n'2) <n na kvadrat>
i pise u t m postupku dobivanja (n-1)+(n-2)+....+1=(n-1)/2
(n-1)/2= n'2-n/2 =O(n'2) ??od kud nam ti n-1 pa na dalje?

-u bubble sortu pise:1 usporedivanje i 4 pridruzivanaj.....i da se unut.petlja izvodi (n-1) puta

usporedbi:(n-1)+(n-2)+(n-3)+...+1=(n-1)/2
zamjena:(n-1)+(n-2)+...+(n-1)/2
slozenost:(n-1)/2+(n-1)/2=(n-1)n=n'2-n==(n'2)


....jel mi moze netko to malo pojasnit ,od kuda nam,znam da ovo brojim usporedbe ,zamjene ...ali kako dobimo ove jedn.gore???


SUTRA MI JE USM!!!...pa molim vas sto prije ako mi mozete bilo tko odg!
hvala

[vsego]

[Gost]

[Gost]

Usmeni kod prof.Drmaca za one koji su polozili pismeni je u petak 6.2.
A oni koji su kolokvirali K-R srijeda 4.2 u 8 h ,a S-Z petak 6.2 u 8h.
I ispiti su u sobi 105.To pise na oglasnoj ploci.
Za prof.Marusic ti nista ne znam.zao mi je.