Algoritmer og kompleksitet

To metoder kan løse samme problem og likevel ikke være i samme klasse. Skal vi pare givere og mottakere i et donasjonsregister, kan vi prøve alle koblinger etter tur, eller vi kan kjøre Ford-Fulkerson. Med fire personer på hver side har opptellingen 24 permutasjoner å gå gjennom, mens Ford-Fulkerson bruker rundt 36 operasjoner. Opptellingen ser billigst ut. Dobler vi til åtte, står det 40 320 mot 70.

Problem, instans og maskin

Et problem er en relasjon mellom input og output. Sortering krever at outputen er en stigende omordning av inputen, og sier ingenting om hvilke tall som kommer inn. En instans er én bestemt input, for eksempel $\langle 6, 8, 3, 5 \rangle$. Problemstørrelsen $n$ er plassen en instans trenger, som regel antall elementer i den.

Kjøretiden er en funksjon av $n$. For at den funksjonen skal si noe som gjelder på andre maskiner enn din egen, regner vi i RAM-modellen: aritmetikk, sammenligning, hopp og oppslag i én celle koster én tidsenhet hver, og instruksjonene utføres etter hverandre. Heltallene har begrenset bredde, om lag $c \lg n$ bits, akkurat nok til å indeksere hele inputen. Vi kan regne med større tall enn det, slik kryptografi gjør, men da holder ikke antagelsen om konstant tid per operasjon lenger.

Vekstrater

Anta ett mikrosekund per operasjon og hundre år til rådighet. Da rekker vi disse problemstørrelsene:

En raskere maskin hjelper mindre enn en bedre algoritme. Kjøper du en maskin som er tusen ganger raskere, flytter du de 17 faktorielle elementene til 20. Bytter du til en kvadratisk algoritme, flytter du dem til titalls millioner.

Asymptotisk notasjon

Vi vil sammenligne vekst uten å måtte telle enkeltoperasjoner. Asymptotisk notasjon gjør det ved å se bort fra konstantfaktorer og lavere ordens ledd.

Grensen trenger bare å holde fra en eller annen $n_0$ og oppover, og $g$ kan skaleres med en konstant først. Derfor er $3n^2 + 100n = \Theta(n^2)$. For stor nok $n$ er $100n$ lite mot det kvadratiske leddet, og faktoren $3$ går inn i $c$.

De to strenge operatorene

$O$ sier at $f$ vokser høyst så raskt som $g$, og tillater at de to vokser like raskt. $2n^2 = O(n^2)$ og $2n = O(n^2)$ er begge sanne, men bare den første er stram. For en øvre grense som ikke er stram bruker vi $o$, og der må $f(n) < c\,g(n)$ holde for enhver $c > 0$, ikke bare for én eneste. Det er en langt sterkere påstand, og den er ekvivalent med at $f(n)/g(n)$ går mot null. Så $2n = o(n^2)$, mens $2n^2 \ne o(n^2)$.

$\omega$ er det samme speilvendt: en nedre grense som ikke er stram, med $c\,g(n) < f(n)$ for enhver $c$. Da vokser $f(n)/g(n)$ over alle grenser, og $f(n) = o(g(n))$ er nøyaktig det samme som $g(n) = \omega(f(n))$.

Alle fem oppfører seg som sammenligning av to tall, og det er den raskeste veien til å huske dem:

Notasjonen dukker også opp midt inne i et uttrykk. Da står den for en ukjent funksjon av den oppgitte ordenen, slik at $n + O(n)$ betyr «$n$ pluss en eller annen funksjon som er $O(n)$». Slike ligninger leses fra venstre mot høyre, og høyresiden må være minst like generell som venstresiden. Derfor stemmer $n + O(n) = O(n)$, mens $O(n) = n + O(n)$ er galt.

Grenser og tilfeller

For hver $n$ finnes det mange instanser, og de koster ulikt, så størrelsen alene bestemmer ikke kjøretiden. Beste tilfelle er den billigste instansen av størrelse $n$, verste tilfelle den dyreste, og gjennomsnittstilfellet er middelet over alle instansene av den størrelsen. Hvert av de tre er en egen funksjon av $n$.

Hvilket tilfelle vi snakker om, og hvor stramt vi begrenser det, er to uavhengige valg. Alle fem operatorene kan brukes på alle tre funksjonene:

Utelater du tilfellet, gjelder påstanden alle instanser. «Insertion-Sort bruker $O(n^2)$» er da riktig, og «$\Omega(n)$» også, mens «$\Theta(n^2)$» er galt: på en sortert tabell bruker den $\Theta(n)$.

Løkkeinvarianter

En løkke gjør det samme trinnet om og om igjen, og korrekthetsbeviset for den er et induksjonsbevis. Vi trenger en påstand om tilstanden som holder ved starten av hver iterasjon.

Initialisering er grunntilfellet og vedlikehold er induksjonssteget. Terminering er det løkker har i tillegg: beviset er verdiløst om løkka aldri stopper.

Svak induksjon antar bare forrige trinn og passer til løkker. Sterk induksjon antar alle mindre tilfeller, og passer når en algoritme kaller seg selv på flere mindre instanser.

Insertion-Sort

Læreboka skriver algoritmen i pseudokode med indekser fra 1. Under står den i Python, med indekser fra 0, slik øvingen krever.

Invarianten er at A[0 : i] er sortert ved starten av hver iterasjon av for-løkka, og består av de elementene som lå der fra begynnelsen. Før første iterasjon er $i = 1$, og utsnittet har ett element. Én iterasjon løfter ut A[i], skyver hvert større element i utsnittet ett hakk mot høyre og setter nøkkelen inn i den ledige plassen, slik at A[0 : i+1] er sortert. Når løkka stopper er utsnittet hele tabellen.

def insertion_sort(A, n):
  for i in range(1, n):
      key = A[i]
      # Sett key inn i den sorterte delen A[0 : i]
      j = i - 1
      while j >= 0 and A[j] > key:
          A[j + 1] = A[j]
          j = j - 1
      A[j + 1] = key
  return A

Den ytre løkka går $n-1$ ganger uansett input. Den indre gjør et sted mellom 0 og $i$ forskyvninger, og det er der forskjellen mellom tilfellene ligger. Er tabellen sortert fra før, er A[j] aldri større enn nøkkelen, while-testen slår feil med én gang, og vi gjør $\Theta(n)$ arbeid totalt.

Sjekk deg selv