Algoritmer og kompleksitet

Faget starter med et språk. Før vi kan si at én algoritme er «bedre» enn en annen, trenger vi en presis modell for hva et problem er, hvordan en algoritme beskrives, og hvordan kjøretid måles uavhengig av maskinen den kjører på.

Problem, instans og maskinmodell

Et problem er den generelle oppgaven (for eksempel «sorter en liste tall»). En instans er én konkret input til problemet, og problemstørrelsen $n$ er målet vi analyserer kjøretiden mot — som regel antall elementer i inputen.

For at kjøretid skal bety det samme på tvers av maskiner regner vi i RAM-modellen (random-access machine): aritmetikk, sammenligning og oppslag i én celle tar konstant tid, og vi teller hvor mange slike grunnoperasjoner algoritmen bruker som en funksjon av $n$. Vi bryr oss ikke om konstantfaktorer eller maskinvare — bare hvordan arbeidet vokser med $n$.

Asymptotisk notasjon

Asymptotisk notasjon er språket for vekst. Den beskriver funksjoner, og sier ingenting i seg selv om hvilket tilfelle (best/average/worst) vi snakker om — det er en egen akse.

De tre tilfellene — best, average og worst-case — er en uavhengig akse: de sier hvilken input vi analyserer, mens notasjonen sier hvor stramt vi begrenser den. Du kan derfor godt si at best-case er $\Omega(n)$ eller at worst-case er $O(n^2)$.

Insertion-Sort og løkkeinvariant

Insertion-Sort bygger en sortert prefiks én nøkkel av gangen, og er pensumnær tidlig nettopp fordi korrektheten følger av en klar løkkeinvariant.

For Insertion-Sort er invarianten: etter iterasjon $i$ er a[0..i] en sortert permutasjon av de opprinnelige elementene der. Den indre løkka løfter ut nøkkelen a[i] og skyver større elementer mot høyre til nøkkelen finner plassen sin.

def insertion_sort(a: list[int]) -> list[int]:
  for i in range(1, len(a)):
      key = a[i]
      j = i - 1
      while j >= 0 and a[j] > key:
          a[j + 1] = a[j]
          j -= 1
      a[j + 1] = key
  return a

Hver nøkkel kan i verste fall skyves forbi hele prefiksen, så worst-case er kvadratisk. Er lista allerede sortert gjøres ingen forskyvninger, og vi får lineær best-case.

Sjekk deg selv