# 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 De generelle og vanligste kjøretidene sortert fra høyest til lavest. || __Kompleksitet__ || __Navn__ || __Type__ || || $\Theta(n!)$ || Factorial || Generell || || $\Omega(k^n)$ || Eksponensiell || Generell || || $O(n^k)$ || Polynomisk || Generell || || $\Theta(n^3)$ || Kubisk || Tilfelle av polynomisk || || $\Theta(n^2)$ || Kvadratisk || Tilfelle av polynomisk || || $\Theta(n \lg n)$ || Loglineær || Kombinasjon av lineær og logaritmisk || || $\Theta(n)$ || Lineær || Generell || || $\Theta(\lg n)$ || Logaritmisk || Generell || || $\Theta(1)$ || Konstant || Generell || # 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. Gode eksempler på rekursive algoritmer er Merge og Quick Sort og binærsøk. Vi finner også ofte rekursive løsninger ved bruk av dynamisk programmering. ## 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 Sortering og søking er to problemstillinger som går igjen enten som problem i seg selv, eller som underproblem. Med sortering mener vi det å arrangere en mengde med objekter i en spesifikk rekkefølge. Med søking mener vi det å finne ett spesifikk objekt i en mengde objekter. ## Sortering Stort sett kategoriserer vi sorteringsalgoritmer inn i to grupper; sammenligningsbaserte og distribuerte/ikke-sammenligninsbaserte. ### Stabilitet En sorteringsalgoritme sies å være stabil dersom rekkefølgen av like elementer i listen som skal sorteres blir bevart i løpet av algoritmen. Altså; dersom vi har listen: $$[B_1, C_1, C_2, A_1]$$ og sorterer den med en eller annen algoritme, og de to like elementene står i samme rekkefølge etter sorteringen, har vi en stabil sorteringsalgoritme. $$[A_1, B_1, C_1, C_2]$$ ### Sammenligninsbaserte sorteringsalgoritmer Alle sorteringsalgoritmer som baserer seg på å sammenligne to elementer for å avgjøre hvilket av de to som skal komme først i en sekvens, kaller vi sammenligningsbasert. Det er vist at $\Omega(n\lg n)$ er en nedre grense for antall sammenligninger en sammenligningsbasert sorteringsalgoritme må gjøre. Med andre ord, det er umulig å lage en sammenligningsbasert sorteringsalgoritme som har bedre worst-case kjøretid enn $O(n\lg n)$. #### Merge sort Merge sort er en sammenligningsbasert sorteringsalgoritme. Den er også et eksempel på en splitt-og-hersk algoritme. || __Best Case__ || __Average Case__ || __Worst Case__ || || $O(n\log n)$ || $O(n\log n)$ || $O(n\log n)$ || Den grunnleggende tankegangen bak algoritmen er som følger: 1. Del opp den usorterte listen i $n$ underlister som hver inneholder ett element. (En liste med ett element er sortert) 2. Flett sammen underlistene. I praksis blir dette gjerne implementert rekursivt. Funksjonen tar ett parameter, nemlig listen som skal sorteres. Dersom listen inneholder kun ett element, kan vi returnere denne listen, siden den allerede er sortert. Dersom den er lenger, splitt den opp i to like store underlister og sorter disse ved å kalle funksjonen rekursivt. Når underlistene kommer tilbake sortert, flett sammen og returner resultatet. I Python: def merge_sort(li): if len(li) < 2: # Dersom vi har en liste med ett element, returner listen, da den er sortert return li sorted_l = merge_sort(li[:len(li)//2]) sorted_r = merge_sort(li[len(li)//2:]) return merge(sorted_l, sorted_r) def merge(left, right): res = [] while len(left) > 0 or len(right) > 0: if len(left) > 0 and len(right) > 0: if left[0] <= right[0]: res.append(left.pop(0)) else: res.append(right.pop(0)) elif len(left) > 0: res.append(left.pop(0)) elif len(right) > 0: res.append(right.pop(0)) return res Merge funksjonen kjører i lineær tid. For å analysere kjøretiden til Merge sort kan vi sette opp følgende rekurrens: $$T(n) = 2T(n/2) + n$$ Altså 2 ganger tiden det tar å sortere en liste av lengde $^n/_2$ pluss tiden det tar å flette de to listene. Se [Masterteoremet](#masterteoremet) for hvordan vi kan løse denne rekurrensen og finne kjøretiden $O(n\log n)$. De fleste implementasjoner av Merge sort er stabile. På grunn av at algoritmen hele tiden lager nye underlister, trenger den $O(n)$ ekstra plass i minnet. #### Quicksort Quicksort er en sammenligningsbasert sorteringsalgoritme, som bruker splitt-og-hersk-taktikken. || __Best Case__ || __Average Case__ || __Worst Case__ || || $O(n\log n)$ || $O(n\log n)$ || $O(n^2)$ || I likhet med [Merge sort](#merge-sort), deler Quicksort problemet opp i mindre deler, og går så rekursivt til verks. Quicksort-funksjonen tar ett parameter, listen som skal sorteres. Tankegangen er som følger: 1. Er det bare ett element i listen? I så fall er listen sortert, returner den. 2. Velg et pivot-element. Det enkleste her kan være å velge det første elementet i lista. 3. Lag to lister, en (lo) som inneholder de elementene fra den opprinnelige lista med tallverdi mindre enn pivot-elementet, en annen (hi) som inneholder de elementene med høyere tallverdi. 4. Sorter lo og hi vha. Quicksort rekursivt. Returner lo + pivot + hi I Python: def quicksort(li): if len(li) < 2: return li pivot = li[0] lo = [x for x in li if x < pivot] hi = [x for x in li if x > pivot] return quicksort(lo) + pivot + quicksort(hi) Kjøretidsanalysen av Quicksort blir noe vanskeligere enn for Merge sort, ettersom størrelsen på listene som sorteres rekursivt vil avhenge av hvilken pivot vi velger. Det å velge en god pivot er en kunst i seg selv. Den naïve fremgangsmåten med å slavisk velge det første elementet, kan lett utnyttes av en adversary, ved å gi en liste som er omvendt sortert som input. I dette tilfellet vil kjøretiden bli $n^2$. Vi kan motvirke dette ved å velge en tilfeldig pivot i stedet. # Graf-algoritmer ## Korteste vei ### Dijkstras algoritme ## Maksimal flyt # Søking Det å finne et spesifikk element i en datastruktur er et utbredt problem. I en liste av tall kan vi f.eks. lete etter medianen eller bare et bestemt tall. I en graf kan vi f.eks. lete etter en måte å komme oss fra ett element til et annet. Søkealgoritmer for grafer er dekt under [Graf-algoritmer](#graf-algoritmer). For å søke i lister, har vi primært to fremgangsmåter; brute force og binærsøk. ## Brute force Denne fremgangsmåten er ganske selvforklarende. Gå gjennom lista (sortert eller ikke) fra begynnelse til slutt og sammenlign hvert ellement mot elementet du ønsker å finne. Med $n$ elementer i lista blir kjøretiden $O(n)$ ## Binærsøk Dersom vi vet at lista vi skal søke i er sortert, kan vi bruke en litt annen strategi. Si at vi leter etter en verdi $a$ i en sortert liste $L$. Vi begynner med å finne det midterste elementet i $L$ og sjekker om det er lik elementet vi leter etter. Dersom ja, returner indeksen, dersom ikke, avgjør om elementet i leter etter er større enn eller mindre enn det midterste, og gjenta deretter prosedyren i den underlista der elementet må være, dersom det i det hele tatt ligger i lista. I Python: def binary_search(li, e):

return -1 middle_val = li[len(li)//2] if e == middle_val: return len(li)//2 elif e < middle_val:

# Dynamisk programmering # Grådige algoritmer # Problemkompleksitet ## P, NP, NPC