Algoritmer og kompleksitet

To metoder kan løse samme problem og likevel ikke være i samme klasse. Skal du pare givere og mottakere i et donasjonsregister, kan du prøve alle koblinger etter tur eller kjøre Ford-Fulkerson. Med $n$ personer på hver side har opptellingen $n!$ koblinger å gå gjennom, mens Ford-Fulkerson gjør i størrelsesorden $n^3$ operasjoner. Med fire personer står det $24$ mot $64$, og opptellingen ser billigst ut. Dobler du til åtte, står det $40\,320$ mot $512$.

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 du 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. Du 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 du 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

For å sammenligne vekst uten å telle enkeltoperasjoner må du se bort fra konstantfaktorer og lavere ordens ledd. Konstantfaktorene forsvinner hvis $g$ får skaleres med en konstant $c$ før sammenligningen. De lavere ordens leddene forsvinner hvis sammenligningen bare trenger å holde fra en $n_0$ og oppover, der det ledende leddet har tatt over. De to kravene gir definisjonen:

Ta $f(n) = n^2 + 100n$ og $g(n) = n^2$. Den nedre grensen holder med $c_1 = 1$ for alle $n$. Den øvre holder med $c_2 = 2$ når $100n \le n^2$, altså fra $n_0 = 100$. Til venstre for $n_0$ ligger $f$ over $2n^2$, og det er tillatt, for definisjonen krever ulikheten bare fra $n_0$ og oppover. Altså er $n^2 + 100n = \Theta(n^2)$, og det lavere ordens leddet $100n$ er borte.

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 du $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:

Analogien holder for transitivitet og for det meste ellers, med ett unntak. To tall kan alltid sammenlignes, men to funksjoner kan mangle et forhold i det hele tatt: $n$ og $n^{1+\sin n}$ er verken $O$ eller $\Omega$ av hverandre, fordi forholdet $n^{\sin n}$ mellom dem svinger mellom omtrent $1/n$ og $n$.

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.

Fung-Sort(A, n)
1 for i = 1 to n
2     for j = 1 to n
3         if A[i] < A[j]
4             swap A[i] and A[j]

Insertion-Sort

Insertion-Sort sorterer slik mange sorterer kort på hånden. Den venstre delen av tabellen er sortert. Hver iterasjon løfter ut det neste elementet, nøkkelen, skyver hvert større element i den sorterte delen ett hakk mot høyre og setter nøkkelen inn i den ledige plassen.

def insertion_sort(A, n):  # indekser fra 0, læreboka teller fra 1
  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

Løkkeinvarianter

Stepperen viser at én tabell blir sortert. For å vise at enhver tabell blir det, bruker du induksjon over iterasjonene, med en påstand om tilstanden ved starten av hver iterasjon. Når løkka er ferdig, skal hele $A$ være sortert og inneholde de elementene som lå der fra begynnelsen. En påstand som gir det til slutt, er at $A[0 .. i - 1]$ ved starten av hver iterasjon består av de elementene som lå der fra begynnelsen, i sortert rekkefølge. Segmentet $A[0 .. i - 1]$ har begge ender med; i Python skrives det A[0 : i].

• Initialisering: før første iterasjon er $i = 1$, og $A[0 .. 0]$ har ett element, så det er sortert.
• Vedlikehold: iterasjonen løfter ut nøkkelen $A[i]$, skyver hvert større element i $A[0 .. i - 1]$ ett hakk mot høyre og setter nøkkelen inn i den ledige plassen. Da er $A[0 .. i]$ sortert, og det er påstanden for neste verdi av $i$.
• Terminering: løkka stopper etter iterasjonen med $i = n - 1$, og da gir vedlikeholdet at $A[0 .. n - 1]$, altså hele tabellen, er sortert.

En slik påstand kalles en løkkeinvariant, og de tre delene er det generelle mønsteret:

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

Beviset for Insertion-Sort er svak induksjon, for vedlikeholdet bruker bare påstanden fra forrige iterasjon. Sterk induksjon antar påstanden for alle mindre tilfeller. Den passer når en algoritme kaller seg selv på instanser som er mindre enn $n - 1$, for eksempel halvparten: beviset for størrelse $n$ bruker da påstanden for $n/2$, ikke for $n - 1$.

Kjøretid

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 instansene 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 arbeidet er $\Theta(n)$ totalt. I en tilfeldig rekkefølge er nøkkelen i snitt mindre enn halvparten av elementene foran seg, så iterasjon $i$ gjør i snitt $i/2$ forskyvninger, til sammen omtrent $n^2/4$, og det er $\Theta(n^2)$. Insertion-Sort bruker $O(1)$ ekstra minne, og like elementer beholder rekkefølgen sin.

Grenser og tilfeller

Insertion-Sort bruker $\Theta(n)$ på en tabell som er sortert fra før og $\Theta(n^2)$ på en som er sortert synkende, så størrelsen alene bestemmer ikke kjøretiden. For hver $n$ finnes det mange instanser, og de koster ulikt. Beste tilfelle er den billigste instansen av størrelse $n$, verste tilfelle den dyreste, og gjennomsnittstilfellet er den forventede kostnaden når instansen trekkes tilfeldig, for sortering med alle rekkefølger like sannsynlige. Hvert av de tre er en egen funksjon av $n$.

Hvilket tilfelle du snakker om, og hvor stramt du begrenser det, er to uavhengige valg. Hver av $O$, $\Omega$ og $\Theta$ kan brukes på hvert av de tre tilfellene, og $o$ og $\omega$ på samme måte. For Insertion-Sort gir det disse grensene:

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)$.

Sjekk deg selv