[Løst] Algoritme og datastruktrer detaljert analyse

[cenenzo]

sdad

Endret 4. februar 2015 av cenenzo

[Djn]

Her må det noen antagelser til, ser jeg. Har du fått noe som helst informasjon, eller må du gjette fra fasitene hva som koster en instruksjon (og ikke), hvorvidt "for i = 1 to 2" kjører en eller to ganger, og hvordan "n/2" blir rundet av?

Endret 28. januar 2015 av Djn

[cenenzo]

sdaa

Endret 4. februar 2015 av cenenzo

[Aleks855]

Tror denne koden er lettere å betrakte når den faktisk settes opp som kode.

 

C(n):

sum = 0;

for i = 1, i <= n-1, i++:

    sum += i;

endfor;

for j = 1, j <= n-1, j++:

    sum += j;

endfor;

return sum;

Første for-løkke vil kjøre n-1 ganger med "<="-operatoren. Med bare "<" ville den kjørt n-2 ganger. Uansett er hele metoden kun avhengig av to enkle for-løkker, som gir kompeksitet . Altså at tidsbruken er lineært avhengig av hvor stor n er.

[Djn]

Husk at han regner på T, ikke O, og altså skal ha det nøyaktige tallet og ikke bare graden.

[cenenzo]

Tror denne koden er lettere å betrakte når den faktisk settes opp som kode.

 

C(n):

sum = 0;

for i = 1, i <= n-1, i++:

    sum += i;

endfor;

for j = 1, j <= n-1, j++:

    sum += j;

endfor;

return sum;

Første for-løkke vil kjøre n-1 ganger med "<="-operatoren. Med bare "<" ville den kjørt n-2 ganger. Uansett er hele metoden kun avhengig av to enkle for-løkker, som gir kompeksitet . Altså at tidsbruken er lineært avhengig av hvor stor n er.

 

så hvis jeg skulle svart det på samme måte som min, så vil linje 2 og 4, ha times: n-1?

[Aleks855]

Husk at han regner på T, ikke O, og altså skal ha det nøyaktige tallet og ikke bare graden.

 

Ser jeg gikk litt foran skjema der ja.

 

 

Tror denne koden er lettere å betrakte når den faktisk settes opp som kode.

 

C(n):

sum = 0;

for i = 1, i <= n-1, i++:

    sum += i;

endfor;

for j = 1, j <= n-1, j++:

    sum += j;

endfor;

return sum;

Første for-løkke vil kjøre n-1 ganger med "<="-operatoren. Med bare "<" ville den kjørt n-2 ganger. Uansett er hele metoden kun avhengig av to enkle for-løkker, som gir kompeksitet . Altså at tidsbruken er lineært avhengig av hvor stor n er.

 

så hvis jeg skulle svart det på samme måte som min, så vil linje 2 og 4, ha times: n-1?

 

 

Nå gitt jeg litt i andre baner enn det oppgaven faktisk spør om, men ja. Jeg leser det som at hver for-løkke kjøres n-1 ganger i C(n).