[zadatak] Vremenska složenost algoritma

Odgovori Nova tema

3 odgovora
4.226 pregleda

[zadatak] Vremenska složenost algoritma 14.11.2008. u 03:52 · pre 218 meseci #1

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.

Code:

for (i=n/2;i>=0;i--)
if (i%2==0)
b[i][i]=1;

Re: [zadatak] Vremenska složenost algoritma 14.11.2008. u 16:37 · pre 218 meseci #2

Ako nesto ne propustam ovo ti je T(n) = n/2 + n/4 = 3n/4 ϵ O(n)

Potpis

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ć

Re: [zadatak] Vremenska složenost algoritma 14.11.2008. u 17:05 · pre 218 meseci #3

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).

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: [zadatak] Vremenska složenost algoritma 15.11.2008. u 18:16 · pre 218 meseci #4

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;

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Forum kao aplikacija na telefonu

Srodne teme