Køretidsanalyse af algoritme

Som den er skrevet i spoergsmaalet koerer den O(n).

Og det er ret nemt at se da loekken altid vil blive koert n gange.

Jeg har lavet en mindre væsentlig fejl da jeg skrev den ind.

i bliver ikke plusset med 1, men med j:

i=1
j=1
while i<=n do
  i = i+j
  j = j+1

Hvilket giver den spændende krølle.

Den er ganske rigtigt O(sqrt(n)).

Og hvordan viser man det?

Der er sikkert en matematisk måde, men her kommer lidt common sense:

Grundliggende vokser i med +1 +2 +3 +4 +5 altså med antal hidtidige gennemløb.

Tænk på i's værdi som arealet af en retvinklet trekant hvor x aksen er antal gennemløb og y aksen er sidste plus.

Så kan man se at:

i = 0.5 * antal gennemløb * sidste tilvækst = 0.5 * antal gennemløb^2

og dermed når i=n:

n = 0.5 * antal gennemløb * sidste tilvækst = 0.5 * antal gennemløb^2

=>

antal gennemløb = sqrt(2*n)

Og derfor er det en O(sqrt(n)) algoritme.

Det er i hvert fald en måde. Jeg ved ikke om den går i en eksamenssituation, men non-the-less en metode.

Tak.

Smid et svar.

kommer her