Studieguide for TDT4120 Algoritmer og datastrukturer

Oversikt

Kompleksitetsanalyse er språket resten av emnet bruker: nesten hver oppgave ber om en kjøretid, og mange ber deg «oppgi svaret i $\Theta$-notasjon». Her handler det om selve notasjonen, om å telle løkker og om de ulike måtene å snakke om kjøretid på. Rekurrenser står under splitt og hersk.

Slik testes dette på eksamen. Kompleksitetsanalyse har minst én egen deloppgave i 18 av 22 sett (2015–2025) og i 8 av de 8 nyeste (2022–2025), og gir 10,4 % av poengene i de nyeste 8. Å forenkle et uttrykk med $O$, $\Omega$ og $\Theta$, eller summen $f(n) + g(n)$, står i 8 av 22 sett og 4 av de 8 nyeste. Løkketelling står i 7 av 22 og 4 av de 8 nyeste. Beste, verste og gjennomsnittlig tilfelle spørres det om i 11 av 22 sett og 5 av de 8 nyeste, ofte knyttet til en bestemt algoritme. Amortisert analyse står i 3 av 22 (2016 des., 2018 des., 2024 aug.).

Notasjonen

• $f(n) = O(g(n))$: $f(n) \le c\,g(n)$ (og $f(n) \ge 0$) for en konstant $c > 0$ når $n \ge n_0$. Øvre grense.
• $f(n) = \Omega(g(n))$: $f(n) \ge c\,g(n) \ge 0$ fra en $n_0$. Dette er en nedre grense.
• $f(n) = \Theta(g(n))$: både $O$ og $\Omega$. Tett grense.
• $o$ og $\omega$ er de strenge variantene: $f(n) = o(g(n))$ betyr at $f(n)/g(n) \to 0$, og $\omega$ at forholdet går mot uendelig.

Har du vist både $O(g)$ og $\Omega(g)$, har du $\Theta(g)$, og $\Theta$ er da det mest informative svaret. Notasjonen er ikke knyttet til et tilfelle: $O$ betyr ikke «verste tilfelle». Beste tilfelle for Insertion-Sort er $\Theta(n)$, og verste er $\Theta(n^2)$. Vokserekkefølgen du må kunne:

$1$ (konstant) $\prec \lg n \prec \sqrt{n} \prec n \prec n \lg n \prec n^2 \prec n^3 \prec 2^n \prec 3^n \prec n!$

Grunntallet i logaritmen spiller ingen rolle, men grunntallet i en eksponent gjør det: $3^n$ er ikke $O(2^n)$.

Regning med notasjon

Et ledd som $O(n^2)$ i et uttrykk står for en ukjent funksjon med den grensen. Summen får den største nedre grensen og den største øvre grensen. Et $\Omega$-ledd har ingen øvre grense, så da har heller ikke summen det. Et $O$-ledd kan være 0 og bidrar ikke til den nedre grensen.

Uttrykk	Resultat	Hvorfor
$O(n^2) + \Theta(n \lg n) + \Omega(\sqrt{n})$	$\Omega(n \lg n)$	$\Theta$-leddet gir nedre grense, $\Omega$-leddet fjerner øvre
$\Theta(n^3) + O(n^4)$	$\Omega(n^3)$ og $O(n^4)$	ingen $\Theta$, grensene er ulike
$\Omega(n^4) / O(n)$	$\Omega(n^3)$	stor teller, liten nevner
$O(n^2) \cdot \Theta(\lg n)$	$O(n^2 \lg n)$	bare øvre grense overlever

Løkketelling

Nøstede løkker ganges, løkker etter hverandre legges sammen. Avhenger den indre løkka av den ytre, summerer du: $\sum_{i=1}^{n} i = n(n+1)/2$. En variabel som dobles eller halveres, gir $\lg n$ runder. En geometrisk sum domineres av siste ledd: $1 + 3 + 9 + \dots + 3^n = (3^{n+1} - 1)/2 = \Theta(3^n)$. Vi regner i RAM-modellen, der hver enkel operasjon (tilordning, sammenligning, aritmetikk på tall av størrelse $O(\lg n)$ bit) tar konstant tid.

Beste, verste og gjennomsnittlig tilfelle

Beste og verste tilfelle er kjøretiden på den gunstigste og den verste input av størrelse $n$. Gjennomsnitt brukes om tre ulike ting:

• Gjennomsnitt over input (average case): snitt over alle input av størrelse $n$, gitt en fordeling. Insertion-Sort er $\Theta(n^2)$ i snitt, likt verste tilfelle, fordi en tilfeldig tabell har omtrent $n^2/4$ par i feil rekkefølge. Et snitt kan altså falle sammen med den ene ytterkanten når konstantene skjules.
• Forventet tid for en randomisert algoritme: forventning over algoritmens egne tilfeldige valg, for hver input. Randomized-Quicksort er forventet $\Theta(n \lg n)$ på alle input.
• Amortisert tid: snitt per operasjon over en hel serie operasjoner på samme datastruktur, uten sannsynlighet.

En nedre grense kan også komme fra antall mulige svar: skal du skille mellom $N$ muligheter med ja/nei-spørsmål, trengs minst $\lceil \lg N \rceil$ spørsmål i verste fall.