# Lenkede lister ## Kjøretider || **Handling** || **Kjøretid** || || Innsetting på starten || O(1) || || Innsetting på slutten || O(n) || || Oppslag || O(n) || || Slette element || oppslagstid + O(1) || # Trær # Traversering # Rekursjon ## Masterteoremet Masterteoremet er en kokebokløsning for å finne kjøretiden til (mange) rekurrenser på formen $$ T(n) = aT(^n/_b) + f(n) \\ a \ge 1, b \ge 1 $$ Denne typen rekurrenser oppstår gjerne i sammenheng med splitt-og-hersk algoritmer, f.eks. Merge sort. Problemet deles opp i $a$ deler av størrelse $^n/_b$, med f(n) arbeid for å gjøre selve oppdelinga, og å sette sammen resultatet av rekursive kall etter at disse er ferdige. I eksempelet med Merge sort, er f(n) arbeidet med å splitte lista i to underlister, og å flette sammen de to sorterte listene etter at de rekursive kallene er ferdige. Det å splitte skjer i konstant tid $\Theta(1)$, mens det å flette sammen tar lineær tid $\Theta(n)$. Vi kan altså sette $f(n) = n$. Siden vi til enhver tid deler listen opp i to deler, hver del $^n/_2$ er henholdsvis $a=2$ og $b=2$. For Merge sort har vi altså: $$ T(n) = 2T(^n/_2) + n $$ Dersom vi ikke allerede visste kjøretiden til Merge sort, kunne vi funnet den ved å løse denne rekurrensen. Å løse rekurrensen kunne vi så brukt Masterteoremet til. Fremgangsmåten for Masterteoremet er som følger: 1. Identifiser $a, b, f(n)$ 2. Regn ut $\log_b a$ 3. Konsulter tabellen under Tabell over de tre tilfellene av Master teoremet:

|| 2 || $f(n)\in \Theta(n^{\log_b a})$ || $T(n) \in \Theta(n^{\log_b a}\lg n)$ ||

$\epsilon > 0$ # Graf-algoritmer # Kjøretidsberegning # Sortering # Korteste vei ## Dijkstras algoritme # Maksimal flyt # Dynamisk programmering # Grådige algoritmer # Problemkompleksitet ## P, NP, NPC