1.2 Kjøretidsanalyse fra kode — løkketelling

Forkunnskaper

- kap. 1.1 — hva $O$ betyr, vekstordningen og regelen om
det dominerende leddet. Alt i dette kapitlet ender med en forenkling som
bruker den.

Er løkker i seg selv ferskt stoff, hjelper disse:

- Løkker: for, while og range — hvordan en løkke teller,
og hva som avgjør hvor mange runder den går.
- Algoritmedefinisjon, pseudokode og kompleksitet (Big-O)
— samme framgangsmåte i et roligere tempo.

Løkke 1 — én løkke, og løkker inni løkker (ca. 12 min)

Start med det aller enkleste. Denne prosedyren legger sammen alle tallene i et
array:

Procedure Sum(A)
  Input:  array A med n tall, indeksert fra 0
  Output: summen av alle tallene i A
  n = A.length
  sum = 0
  for i = 0 to n-1:
      sum = sum + A[i]
  return sum

Løkka går $n$ runder. Inni løkka står én linje som gjør en fast mengde arbeid:
ett oppslag og én addisjon, uansett hvor stort arrayet er. Total: $n$ ganger et
konstant arbeid, altså $O(n)$.

Det er hele metoden. Alt annet i dette kapitlet er varianter av det samme
spørsmålet: hvor mange ganger kjører den innerste linja?

Løkke 2 — den konstante indre løkka (ca. 8 min)

Her ligger den fella som koster flest poeng på sjanger B, og den er lett å se
når du først vet om den.

Procedure NullstillNaboer(A)
  Input:  array A med n tall, indeksert fra 0
  Output: A der hvert element er erstattet av summen av seg selv og de ti neste
  n = A.length
  for i = 0 to n-1:
      s = 0
      for j = 0 to 9:
          if i + j < n:
              s = s + A[i + j]
      A[i] = s

Det ser ut som to nøstede løkker, og to nøstede løkker er $O(n^2)$. Men se på
den indre: den går fra 0 til 9. Alltid ti runder, uansett om arrayet har
åtte eller åtte millioner elementer.

Ti er en konstant. Den innerste linja kjører derfor $10n$ ganger, og $10n$ er
$O(n)$.

Løkke 3 — når tellevariabelen dobles eller halveres (ca. 12 min)

— naturlig pausepunkt —

Den andre store gjenkjenningsoppgaven er løkker som ikke går ett steg av
gangen, men ganger eller deler.

j = 1
while j < n:
    x = x + 1
    j = j * 2

Med $n = 8$ tar j verdiene 1, 2, 4 — tre runder, for ved $j = 8$ er ikke
lenger j < n. Med $n = 16$ blir det fire runder, med $n = 32$ fem, med
$n = 128$ sju.

Legg merke til hva som skjedde: vi doblet $n$ fra 8 til 16, og antall runder
økte med én. Doblet vi $n$ igjen, økte det med én til. Det er nøyaktig
definisjonen av en logaritme: antall doblinger fra 1 opp til $n$ er
$\lfloor \log_2 n \rfloor + 1$.

Løkka er altså $O(\log n)$ — og det gjelder like mye den motsatte veien:

Løkke 4 — sekvens, og løkker som starter der den ytre står (ca. 10 min)

To siste mønstre, og så har du hele repertoaret.

Sekvens. Står to løkker etter hverandre, legges de sammen — og den verste
overlever:

for i = 0 to n-1:
    for j = 0 to n-1:
        x = x + 1

for i = 0 to n-1:
    y = y + 1

Den første blokken er $O(n^2)$, den andre er $O(n)$. Til sammen $n^2 + n$, og
det dominerende leddet er $n^2$. Svaret er $O(n^2)$.

Trekantløkker. Denne varianten dukker opp hver gang koden skal se på alle
par uten å telle samme par to ganger:

for i = 0 to n-1:
    for j = i to n-1:
        x = x + 1

Den indre løkka går $n$ runder når i er 0, $n-1$ runder når i er 1, og til
slutt bare 1 runde. Summen er $\displaystyle n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2}$, som
er $O(n^2)$ — halvparten av arbeidet til to fulle løkker, men samme orden,
fordi $\displaystyle \frac{1}{2}$ er en konstant.

Løkke 5 — sammensatte snutter og et blikk på rekursjon (ca. 10 min)

På eksamen kommer sjanger B som regel med to eller tre nivåer der minst ett er
en dobling. Da er framgangsmåten uendret: ta ett nivå om gangen, innenfra og ut.

Et sideblikk: rekursjon

Rekursjon — at en prosedyre kaller seg selv — er pensum i IN2010, og du
kommer til å skrive mye av den i tre- og grafkapitlene. Til kjøretidsanalyse
gjør vi likevel akkurat det samme som med løkker: teller arbeid, ikke setter
opp ligninger.

Ett mønster er verdt å kjenne igjen, mest fordi det har dukket opp i eldre sett:

Procedure Proc(n)
  Input:  et heltall n
  Output: ingenting; utfører et fast stykke arbeid per kall
  if n <= 0:
      return
  gjør en fast mengde arbeid
  Proc(n-1)
  Proc(n-1)

Hvert kall lager to nye kall med argumentet redusert med bare 1. Antall kall
dobles for hvert nivå: 1, 2, 4, 8 og så videre nedover $n$ nivåer. Totalt blir
det $2^{n+1} - 1$ kall — for $n = 10$ er det 2047, for $n = 20$ over to
millioner. Kjøretiden er $O(2^n)$.

Kontrolltelling: for $n = 1$ til 5 er antall kall 3, 7, 15, 31 og 63 — hvert
tall er ett mindre enn en toerpotens, akkurat som formelen sier.

Avgrensning, og den er verdt penger: rekurrensligninger, substitusjonsmetoden
og de generelle teoremene for å løse slike ligninger er ikke IN2010-pensum. Møter du dem i en generell
algoritmebok, kan du hoppe over kapitlet. I dette faget analyserer du rekursjon
ved å telle: hvor mange kall blir det, og hvor mye arbeid gjør hvert kall?