Begreper

01 Grunnlag

Problem og instans #

Et problem er relasjonen mellom input og output. En instans er én bestemt input. Problemstørrelsen $n$ er plassen en instans trenger, som regel antall elementer.

RAM-modellen #

Random-access machine: en idealisert maskin der aritmetikk, sammenligning, hopp og oppslag i én celle koster én tidsenhet hver, og instruksjonene utføres etter hverandre. Heltallene er om lag $c \lg n$ bits brede.

Asymptotisk notasjon #

Et språk for vekst som ser bort fra konstantfaktorer og lavere ordens ledd. Oppfører seg som sammenligning av tall: $O$ er $\le$, $\Omega$ er $\ge$, $\Theta$ er $=$, $o$ er $<$ og $\omega$ er $>$. De to siste krever ulikheten for enhver konstant $c > 0$, ikke bare for én.

Beste, verste og gjennomsnittlige tilfelle #

Tre funksjoner av $n$: kjøretiden for den billigste instansen av størrelse $n$, for den dyreste, og middelet over alle. Hvilket tilfelle det gjelder er uavhengig av hvilken asymptotisk operator som brukes på det.

Løkkeinvariant #

En påstand om tilstanden som holder ved starten av hver iterasjon. Vises med initialisering, vedlikehold og terminering, og er induksjonsbeviset for at løkka er korrekt.

Insertion-Sort #

Sorterer ved å holde $A[0 : i]$ sortert og sette $A[i]$ inn på rett plass i det utsnittet. Bruker $\Theta(n)$ i beste tilfelle og $\Theta(n^2)$ i verste, og sorterer på plass.