# Lineære datastrukturer ## Lenkede lister  En lenket liste er en enkel lineær datastruktur som representerer elementer i sekvens. Tanken bak strukturen er at rekkefølgen på elementer opprettholdes ved at hvert element peker til det neste i rekkefølgen (se figuren over). Forklart med kode: class Node: def __init__(self): self.value = None self.next = None n1 = Node() n2 = Node() n3 = Node() n1.value = 1 n2.value = 2 n3.value = 3 n1.next = n2 n2.next = n3 Med koden ovenfor vil strukturen være n1 -> n2 -> n3 Vi kan også ha dobbeltlenkede lister, der hver node inneholder en verdi og peker til både forrige og neste node. ### Kjøretider || **Handling** || **Kjøretid** || || Innsetting på starten || O(1) || || Innsetting på slutten || O(n) || || Oppslag || O(n) || || Slette element || oppslagstid + O(1) || # Kjøretidsberegning # Rekursjon Rekursjon er en problemløsningsmetodikk som baserer seg på at løsningen på et problem er satt sammen av løsningene til mindre instanser av samme problem. Denne teknikken kommer til å gå igjen i mange av algoritmene i pensum. Et av de aller vanligste eksemplene på rekursivitet er Fibonaccitallene, definert som: $$F(n) = F(n-1) + F(n-2)\\ F(0) = 0, F(1) = 1$$ Fibonaccitall $n$ er altså definert som summen av de to foregående Fibonaccitallene.

## 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: || **Tilfelle** || **Krav** || **Løsning** || || 1 || $f(n)\in O(n^{\log_b a-\epsilon})$ || $T(n) \in \Theta(n^{\log_b a})$ || || 2 || $f(n)\in \Theta(n^{\log_b a})$ || $T(n) \in \Theta(n^{\log_b a}\lg n)$ || || 3 || $f(n)\in \Omega(n^{\log_b a+\epsilon})$|| $T(n) \in \Theta(f(n))$ || $\epsilon > 0$ Vi fortsetter eksempelet med Merge sort. Vi har funnet $a=2, b=2, f(n)=n$, da må $\log_b a = \log_2 2 = 1$. Vi har altså tilfelle 2, $f(n) \in \Theta(n^1)$, med løsning $T(n) \in \Theta(n\lg n)$. ### Eksempel Enda et eksempel, hentet fra kontinuasjonseksamen 2009: Løs følgende rekurrens. Oppgi svaret i asymptotisk notasjon. Begrunn svaret kort. $$ T(n) = 2T(^n/_3) + ^1/_n $$ Vi har $a = 2, b = 3, f(n) = n^{-1}$. Det gir $\log_b a = \log_3 2 \approx 0.63$. Siden $f(n) = n^{-1}$ er $O(n^{.63})$, har vi tilfelle 1 og løsningen $T(n) \in \Theta(n^{.63})$. # Sortering og søking # Graf-algoritmer # Sortering # Korteste vei ## Dijkstras algoritme # Maksimal flyt # Dynamisk programmering # Grådige algoritmer # Problemkompleksitet ## P, NP, NPC