Algoritmer, kjøretid og asymptotisk notasjon

Hva en algoritme egentlig er

En algoritme er en endelig, presis oppskrift som tar en inndata og produserer ønsket utdata på et endelig antall steg. «Endelig» er nøkkelordet: oppskriften må stoppe. «Presis» betyr at hvert steg er entydig, uten rom for skjønn. En matoppskrift er nesten en algoritme, men «smak til med salt» er for vagt — en algoritme tolererer ikke slikt.

Det interessante spørsmålet er sjelden om en algoritme virker, men hvor mye arbeid den krever. To algoritmer kan løse samme problem og gi nøyaktig samme svar, men den ene kan være ferdig på et sekund der den andre bruker en time. Hele dette kapitlet handler om å måle den forskjellen på en måte som er uavhengig av hvilken maskin koden tilfeldigvis kjører på.

RAM-modellen: hva ett steg koster

For å telle arbeid trenger vi en modell av hva en maskin kan gjøre. ram-modellen er en idealisering der noen få grunnoperasjoner — addisjon, sammenligning, å lese eller skrive én verdi i minnet, hoppe til en annen linje — hver koster én tidsenhet, uansett hvilke tall som er involvert.

Det er en forenkling, men en nyttig en. I virkeligheten er ikke alle operasjoner like raske, og moderne maskiner har cache-hierarkier og parallellitet vi ser bort fra. Men poenget er ikke å forutsi sekunder på klokka. Poenget er å telle antall grunnoperasjoner som en funksjon av hvor stor inndataen er, slik at vi kan sammenligne algoritmer rettferdig. En algoritme som gjør dobbelt så mange operasjoner, er dobbelt så treg uansett hvor rask maskinen er.

Vekst er det som teller

La oss si at vi har talt opp at en algoritme bruker $3n^2+5n+20$ operasjoner på en inndata av størrelse $n$. Hva av dette betyr noe? For små $n$ kan konstantleddet 20 dominere. Men algoritmer kjøres på stor inndata — det er der treghet gjør vondt — og for stor $n$ er det $n^2$-leddet som tar over fullstendig. Når $n=1000$ er $3n^2$ tre millioner, mens $5n+20$ knapt er fem tusen. Lavordens-leddene og konstantfaktoren drukner.

Derfor bryr vi oss om asymptotisk notasjon: hvordan kjøretiden vokser når $n$ blir stor, der vi med vilje ignorerer konstanter og lavordens-ledd. Figuren viser hvorfor. Tre funksjoner — $n$, $n\lg n$ og $n^2$ — starter nokså likt for små $n$, men spriker dramatisk når $n$ vokser. Forskjellen mellom dem er det som avgjør om en algoritme skalerer eller ikke. En konstantfaktor flytter en kurve litt, men endrer aldri hvilken kurve som til slutt ligger øverst.

O, Omega og Theta

Asymptotisk notasjon har tre hovedformer, og de svarer til tre forskjellige påstander.

store o er en øvre grense. ƒstore o (øvre grense) sier formelt at $f=O(g)$ dersom $f$ fra et punkt og utover ikke vokser raskere enn $g$, opp til en konstant faktor. I dagligtale: «algoritmen bruker høyst så mye tid». Når noen sier at en sortering er $O(n^2)$, lover de at den aldri blir verre enn kvadratisk — men de utelukker ikke at den kan være raskere.

store omega er det motsatte: en nedre grense. ƒstore omega (nedre grense) sier at $f=\Omega (g)$ når $f$ vokser minst like raskt som $g$. «Algoritmen bruker minst så mye tid.» Det er en garanti om at noe ikke kan gå raskere enn en viss grense.

store theta kombinerer begge. ƒstore theta (tett grense) sier at $f=\Theta (g)$ betyr at $f$ er både $O(g)$ og $\Omega (g)$ — den vokser nøyaktig som $g$, verken raskere eller saktere asymptotisk. Dette er den sterkeste og mest presise påstanden, og den vi helst vil frem til. Sier vi at Merge-Sort er $\Theta (n\lg n)$, har vi klemt kjøretiden fast mellom en øvre og en nedre grense av samme orden.

Det finnes også strenge varianter, $o$ og $\omega$ (lille o og lille omega), som sier at $f$ vokser strengt saktere eller raskere enn $g$. De brukes sjeldnere, men er greie å kjenne til. En egenskap som forenkler livet, er ƒtransitivitet for o: grensene oppfører seg som ulikheter og kan lenkes sammen. Er $f=O(g)$ og $g=O(h)$, så er $f=O(h)$.

Beste, verste og gjennomsnittlig tilfelle

Samme algoritme kan bruke ulik tid på ulik inndata av samme størrelse. Derfor skiller vi beste, verste og gjennomsnittlig tilfelle. Verste tilfelle er den inndataen som tvinger frem mest arbeid; det er den vi oftest oppgir, fordi den gir en garanti — algoritmen blir aldri verre enn dette. Beste tilfelle er den gunstigste inndataen, og gjennomsnittstilfellet er forventningen over en fordeling av inndata.

En vanlig felle: gjennomsnittet er ikke snittet av beste og verste. Det krever at vi vet noe om hvilke inndata som er sannsynlige, og må regnes ut som en forventningsverdi. For mange algoritmer ligger gjennomsnittet nærmere verste enn beste.

For Insertion-Sort er det lærerikt å se hvorfor. Når en ny nøkkel skal plasseres, må den i snitt forbi omtrent halvparten av de allerede sorterte elementene, dersom inndataen er tilfeldig stokket. Halvparten av kvadratisk arbeid er fortsatt kvadratisk arbeid — gjennomsnittstilfellet er også $\Theta (n^2)$. Det er bare den allerede sorterte inndataen som slipper unna med lineær tid. Lærdommen er at en algoritmes beste tilfelle kan se forlokkende ut uten å si noe om hva du faktisk får i praksis.

Insertion-Sort, steg for steg

La oss gjøre dette konkret med insertion-sort, en enkel sortering som etterligner måten mange ordner en kortstokk på hånda. Du holder de første kortene sortert, plukker opp det neste, og skyver det bakover forbi de større til det ligger på rett plass. Her er den i en 0-indeksert pseudokode:

Insertion-Sort(A):
    for i fra 1 til lengde(A) - 1:
        nøkkel = A[i]
        j = i - 1
        så lenge j >= 0 og A[j] > nøkkel:
            A[j + 1] = A[j]     # skyv det større elementet ett hakk høyre
            j = j - 1
        A[j + 1] = nøkkel        # legg nøkkelen i hullet som oppstod

Den ytre løkka går gjennom elementene fra venstre. For hvert nytt element (nøkkelen) skyver den indre løkka alle de større naboene til venstre ett hakk mot høyre, helt til den finner plassen der nøkkelen hører hjemme.

Figuren sporer algoritmen på [5, 2, 4, 1]. Etter hvert steg er den venstre delen av arrayet ferdig sortert, og den vokser med ett element om gangen til hele arrayet er på plass.

Hvorfor kjøretiden blir som den blir

Kostnaden til Insertion-Sort ligger i den indre løkka — hvor langt må hver nøkkel skyves? ƒinsertion-sort, verste tilfelle er verste tilfelle, $\Theta (n^2)$, og det inntreffer når inndataen er sortert baklengs. Da må hver nye nøkkel forbi alle de foregående, og totalt antall forskyvninger blir $1+2+\cdots +(n-1)$ — nettopp den aritmetiske summen fra forrige kapittel, som er $\Theta (n^2)$.

ƒinsertion-sort, beste tilfelle er beste tilfelle, $\Theta (n)$, og inntreffer når inndataen allerede er sortert. Da finner den indre løkka umiddelbart at nøkkelen er på plass, gjør ingen forskyvninger, og hver runde koster bare én sammenligning. Det er en fin illustrasjon av at beste og verste kan være vidt forskjellige. Mer generelt gir ƒsum av polynom regelen for nøstede løkker: $d$ nøstede løkker som hver teller opp til $n$, gjør $\Theta (n^{d+1})$ arbeid.

Løkkeinvariant: hvorfor svaret blir riktig

At en algoritme er rask hjelper lite hvis den er feil. En løkkeinvariant er verktøyet vi bruker for å bevise at en løkke gjør det den skal. Det er en påstand som er sann før løkka starter, bevares av hver iterasjon, og som ved slutten gir oss konklusjonen vi vil ha.

For Insertion-Sort er invarianten: når den ytre løkka starter på indeks $i$, er elementene fra 0 til $i - 1$ allerede sortert seg imellom. Den er trivielt sann før første runde (ett element er sortert i seg selv), den bevares av hver runde (vi setter nettopp inn det nye elementet på rett plass blant de sorterte), og når løkka er ferdig dekker den hele arrayet — som da er sortert. Tre små argumenter, og korrektheten er bevist. Denne tankegangen — oppstart, bevaring, avslutning — er det samme mønsteret vi bruker for å bevise langt mer innfløkte algoritmer senere.