Verktøykassa: notasjon og forkunnskaper

Hvorfor et eget verktøykapittel

Resten av faget handler om å lage algoritmer og måle hvor mye arbeid de krever. Før vi kan det, trenger vi et felles språk. Det er ingen poeng i å diskutere om en sortering bruker «omtrent halvparten så lang tid» hvis vi ikke er enige om hva en logaritme er, eller hva det betyr at en graf har mange kanter. Dette kapitlet er ikke ny teori — det er notasjonen og de grunnleggende strukturene som alt det andre hviler på. Du har sett mye av det før; her samler vi det og knytter hvert verktøy til hvorfor det dukker opp senere.

Tak, gulv og rester

Algoritmer deler stadig en mengde i (nesten) like store deler. Deler du 7 elementer i to, får du ikke 3,5 på hver side — du må runde. tak og gulv er de to måtene å runde et reelt tall til et heltall på. Gulvet $\lfloor x\rfloor$ runder nedover, taket $\lceil x\rceil$ oppover. For et tall som allerede er helt, er de like.

For $x=2,7$ er $\lfloor x\rfloor =2$ og $\lceil x\rceil =3$. Den nyttige egenskapen er at de ligger tett: ƒgulv og tak sier at avstanden mellom tak og gulv aldri overstiger 1. Det er nettopp denne egenskapen som gjør at vi kan dele en liste på 7 i en venstrehalvdel på $\lfloor 7/2\rfloor =3$ og en høyrehalvdel på $\lceil 7/2\rceil =4$ uten å miste noe.

Nær slekt er modulo: resten ved heltallsdivisjon. $17\mathrm{mod}5=2$ fordi $17=3\cdot 5+2$. Formelt skriver vi ƒmodulo, men den daglige nytten er enkel: modulo pakker et hvilket som helst heltall inn i intervallet $0$ til $n-1$. Vil du fordele nøkler på 8 bøtter, regner du nøkkel mod 8 og lander alltid på en bøtte mellom 0 og 7. Det er kjernen i hvordan en hashtabell finner plassen sin.

Logaritmer: å telle halveringer

logaritme er den enkeltdetaljen som forvirrer flest, og samtidig den vi bruker oftest. ${\log }_{b}x$ er svaret på spørsmålet: hvor mange ganger må jeg gange $b$ med seg selv for å nå $x$? Siden $2^{10}=1024$, er ${\log }_{2}1024=10$.

I algoritmer betyr en toerlogaritme nesten alltid det samme konkrete: hvor mange ganger kan jeg halvere $n$ før jeg står igjen med 1? Har du 1000 elementer og kaster halvparten i hvert steg, er du nede på ett element etter omtrent 10 steg, fordi $\lg 1000\approx 10$. Vi skriver $\lg$ for toerlogaritmen og bruker den så ofte at den fortjener sitt eget symbol.

ƒlogaritmeregler samler de to reglene du trenger oftest. Den første gjør multiplikasjon om til addisjon: $\log (xy)=\log x+\log y$. Den andre — basebytte — forklarer hvorfor vi kan være likegyldige til basen i kjøretidsanalyse. Å bytte fra base 2 til base 10 ganger bare hele uttrykket med en fast konstant, og konstanter forsvinner i den asymptotiske notasjonen vi møter i neste kapittel. Derfor skriver vi gjerne bare «logaritmisk» uten å spesifisere base.

Summer som dukker opp overalt

To summer går igjen så ofte at du bør kjenne dem igjen på flekken. Den første er ƒaritmetisk sum (håndtrykk), summen av de $n$ første heltallene. Den kalles ofte håndtrykkssummen: skal $n$ personer hilse på hverandre én gang hver, blir det $1+2+\cdots +(n-1)$ håndtrykk. Den lukkede formen $\frac{n(n+1)}{2}$ er hele grunnen til at en dobbel løkke der den indre teller opp mot den ytre, koster $\Theta (n^2)$ og ikke noe mindre. Vi støter på det igjen når vi analyserer Insertion-Sort.

Den andre er ƒgeometrisk sum, der hvert ledd er en fast faktor ganger det forrige: $1+2+4+8+\dots$. Det kontraintuitive er at summen domineres helt av det siste, største leddet. $1+2+4+\cdots +1024$ blir $2047$ — knapt mer enn det dobbelte av det største leddet alene. Den innsikten forklarer hvorfor tabelldobling forblir billig, noe vi kommer til nederst.

Fakultet

fakultet skrives $n!$ og er produktet $1\cdot 2\cdot 3\cdots n$. Det teller hvor mange måter du kan stokke om $n$ ting på: tre bøker kan stilles i $3!=6$ rekkefølger. Tallet vokser voldsomt — $10!$ er allerede over tre millioner, og $20!$ er astronomisk. Når en algoritme må prøve alle rekkefølger av inndata, er den $\Theta (n!)$, og da er den i praksis ubrukelig for alt annet enn små $n$. Fakultet er altså mest et faresignal: ser du det i en kjøretid, har du sannsynligvis ikke en effektiv algoritme.

Mengder og grafer

En mengde er en uordnet samling av distinkte elementer. «Uordnet» betyr at $\{3,1,2\}$ og $\{1,2,3\}$ er nøyaktig samme mengde, og «distinkte» at et element ikke kan forekomme to ganger. Mengder gir oss et presist språk for å snakke om delmengder, snitt og union — og ikke minst for å definere grafer.

En graf er et par $(V,E)$: en mengde noder $V$ og en mengde kanter $E$ mellom dem. Grafer modellerer relasjoner — veier mellom byer, venner i et nettverk, avhengigheter mellom oppgaver. En graf kan være urettet (kantene går begge veier) eller rettet (kantene er enveispiler), og kantene kan ha vekter (en avstand, en kostnad).

grad er antall kanter som møter en node. I figuren har node D grad 3, fordi tre kanter ender der. I rettede grafer skiller vi inn-grad og ut-grad. To fakta om grad er verdt å huske. ƒhåndtrykkslemma sier at summen av alle gradene er nøyaktig det dobbelte av antall kanter — hver kant teller jo to ganger, én gang i hver ende. Og ƒmaks antall kanter gir taket på hvor mange kanter en enkel graf med $|V|$ noder kan ha: hvert par kan ha høyst én kant. En graf nær dette taket kaller vi tett, en med langt færre kanter glissen. Skillet avgjør senere hvilken algoritme som lønner seg.

Datastrukturer: hvor ligger dataene

Hvordan vi lagrer data avgjør hva som er billig og hva som er dyrt. Et array er en sammenhengende blokk minne. Fordelen er konstant-tids tilgang: element nummer $i$ ligger på en adresse vi regner ut direkte, så a[5000] koster like lite som a[0]. Ulempen er innsetting midt i: skal du dytte et nytt element inn foran, må alt bak flyttes ett hakk.

En lenket liste snur avveiningen. Her er hvert element en node som peker videre til den neste, og nodene kan ligge spredt i minnet. Innsetting og sletting er billig — du flytter bare et par pekere — men oppslag er dyrt, for å finne element nummer $i$ må du følge pekerne ett steg om gangen fra starten.

En hashtabell gir det beste fra begge i typiske tilfeller: forventet konstant tid for oppslag, innsetting og sletting. Den bruker en hashfunksjon til å regne om hver nøkkel til en bøtteindeks — gjerne nettopp med modulo, som vi så over — og legger elementet der. Kollisjoner (to nøkler i samme bøtte) håndteres, men ideelt sett spres nøklene jevnt slik at hver bøtte holder få elementer.

Til slutt: en abstrakt datatype skiller hva en struktur kan gjøre fra hvordan den gjør det. En kø lover «først inn, først ut», uansett om den er bygget på et array eller en lenket liste. Det lar oss resonnere om algoritmer på et høyere nivå, og bytte implementasjon under panseret uten å endre logikken over.

Tabelldobling: amortisert kostnad

Et array har fast størrelse, men ofte vet vi ikke på forhånd hvor mange elementer vi får. tabelldobling løser det: når arrayet blir fullt, lager vi et nytt som er dobbelt så stort og kopierer alt over. Den enkelte doblingen er dyr — å kopiere $n$ elementer koster $\Theta (n)$ — men den skjer stadig sjeldnere, fordi kapasiteten dobles hver gang.

Her kommer den geometriske summen til nytte. Setter vi inn $n$ elementer, er den samlede kopieringskostnaden over alle doblingene $1+2+4+\cdots +n$, som vi vet domineres av det siste leddet og blir omtrent $2n$. Fordelt på $n$ innsettinger gir det ƒamortisert kostnad ved tabelldobling: konstant kostnad per innsetting i snitt. Dette kaller vi amortisert analyse — vi ser ikke på det verste enkelttilfellet, men på gjennomsnittet over en hel sekvens av operasjoner. Det er nettopp dette knepet som lar et dynamisk array late som om det vokser gratis.