Brojanje koraka u C kodu

Odgovori Nova tema

2 odgovora
2.070 pregleda

Brojanje koraka u C kodu 28.08.2012. u 14:27 · pre 172 meseci #1

Zna se da je n paran prirodan broj. Odrediti broj koraka i vremensku slozenost u O notaciji sledeceg fragmenta C koda:

Code (c):

for(s = 0, i = 0; i<n; i=i+2)

  for(j = 0; j<n; j = j+1)

    for(k = 1; k<n; k = k*3)

      s = s + i*j+k;

ja sam poceo sa 2+n(1+2)*(1+n+2)*(1+n-1+2)*2, da li je ovo dobro? Ako nije bio bih zahvalan ako neko moze da resi..

Re: Brojanje koraka u C kodu 28.08.2012. u 17:29 · pre 172 meseci #2

Ako je l najveći ceo broj takav da je 3^l<n, odnosno $l=[\log_3(n-1)]$ , gde je $[x]$ oznaka za najveći ceo broj koji nije veći od $x$ , onda se petlja po k za ma koje fiksirane vrednosti i i j izvrši po l+1 puta. Petlja po j se izvrši za svaku vrednost od i po n puta, a petlja po i n/2 puta. Dakle,

$(n/2)n([\log_3(n-1)]+1)=n^2([\log_3(n-1)]+1)/2$ .

Potpis

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

Re: Brojanje koraka u C kodu 29.08.2012. u 13:56 · pre 172 meseci #3

Hvala puno.

Prijavite se da biste odgovorili u ovoj temi.Prijava Registracija

Srodne teme