Može li neko da mi odredi vremensku složenost sledećeg fragmenta koda. Potrebno je broj koraka prikazati precizno u obliku polinomijalnog izraza i u notaciji sa velikim O.
Ako nesto ne propustam ovo ti je T(n) = n/2 + n/4 = 3n/4 ϵ O(n)
Sloba je za 12 godina promenio antropološki kod srpskog naroda. On je od jednog naroda koji je bio veseo, pomalo površan, od jednog naroda koji je bio znatiželjan, koji je voleo da vidi, da putuje, da upozna,
od naroda koji je bio kosmopolitski napravio narod koji je namršten, mrzovoljan, sumnjicav, zaplašen, narod koji se stalno nešto žali, kome je stalno neko kriv… - Z.Đinđić
Petlja se izvrsava n/2 + 1 puta, a dodela 2(n/4) + 1 puta. Zapravo, vreme je a*(n/2+1) + b*(2(n/4)+1), gde je b vreme dodele, dok je a vreme izvrsavanja svega ostalog u petlji. Sve skupa je O(n). Pritom je "/" oznaka za celobrojno delenje sa odbacivanjem ostatka (25 / 6 = 4).
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
A jel moze nemo meni da odredi vremensku složenost sledećeg fragmenta koda. Potrebno je isto broj koraka prikazati precizno u obliku polinomijalnog izraza i u notaciji sa velikim O.
Code:
for ( i = 0; i< n/2;i++)
for (j =0; j<n; j++)
b[i][j]=1;
[Ovu poruku je menjao wujic dana 15.11.2008. u 18:51 GMT+1]
[zadatak] Vremenska složenost algoritma
Registrovani: 3 ( vjova, Predrag Supurovic, Nebojsa Milanovic )