Midtsemester TDT4120

Algoritmer og Datastrukturer

Håvard Krogstie - høsten 2021

1

Induksjon

Mattematisk bevismetode

Designe algoritmer
Bevise korrekthet til algoritmer
Regne på kjøretid til algoritmer

$\mathrm{P}(n) \coloneqq \text{påstand for et gitt heltall }n$

Grunntilfelle

$\mathrm{P}(0)$

+

Induktivt steg

$\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$

2

Induksjon - Hetlands stige

Vi har bevist

Grunntilfelle
$\mathrm{P}(0)$
Induktivt steg
$\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$

Vi kan sette inn en hvilken som helst $k$ $k$ .
- $\mathrm{P}(0) \Rightarrow \mathrm{P}(1)$
- $\mathrm{P}(1) \Rightarrow \mathrm{P}(2)$
- $\mathrm{P}(2) \Rightarrow \mathrm{P}(3)$
- $\mathrm{P}(3) \Rightarrow \mathrm{P}(4)$
- $\ldots$

3

Induksjon Eksempel

Sum av oddetall

$\mathrm{P}(n) \coloneqq \hspace{1cm} \text{summen av de første }n \text{ oddetallene} = n^2 \hspace{1cm}$

$\sum_{i=1}^n 2i-1 = {n}^2$

altså prøver vi å si at:

$1 + 3 + 5 + \cdots + (2n-1) = {n}^2$

Hvordan viser vi dette?

4

Induksjon Eksempel

Sum av oddetall (cont.)

$\mathrm{P}(n) \coloneqq \hspace{1cm} \text{summen av de første }n \text{ oddetallene} = n^2 \hspace{1cm}$

Grunntilfelle

$\mathrm{P}(0) \coloneqq \hspace{1cm} \text{summen av de første }0 \text{ oddetallene} = 0^2 \hspace{1cm}$

5

Induksjon Eksempel

Sum av oddetall (cont.)

$\mathrm{P}(n) \coloneqq \hspace{1cm} \text{summen av de første }n \text{ oddetallene} = n^2 \hspace{1cm}$

Grunntilfelle $\mathrm{P}(0)$ ✔

Induktivt steg

Vi antar at $\mathrm{P}(k-1)$ er sant. Dette kalles induksjonshypotesen.

Vi skal vise at det medfører $\mathrm{P}(k)$ .

$\text{summen av de første }k-1 \text{ oddetallene} = (k-1)^2$

$\text{summen av de første }k \text{ oddetallene} = (k-1)^2 + (2k-1)$

$\text{summen av de første }k \text{ oddetallene} = k^2$

$\underline{\underline{\mathrm{P}(k)}}$

6

Induksjon Eksempel

Sum av oddetall (cont.)

$\mathrm{P}(n) \coloneqq \hspace{1cm} \text{summen av de første }n \text{ oddetallene} = n^2 \hspace{1cm}$

Grunntilfelle $\mathrm{P}(0)$ ✔

Induktivt steg $\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$ ✔

Vi har nå bevist $\mathrm{P}(n)\ \forall n\in\mathbb{N}$

7

Induksjon og algoritmer

Hva har induksjon med algoritmer å gjøre?

Domenet til en algoritme er mengden med gyldige input-instanser.

$\mathrm{MAKS}(\mathrm{LISTE}): \text{Det største tallet i LISTE}$

Domenet: Alle lister med tall

Problem: lister kan være vilkårlig store!
- Hvordan bevise at algoritmen fungerer for alle mulige liste-lengder $n$ ?

$\mathrm{P}(n) \coloneqq \hspace{1cm} \mathrm{MAKS(LISTE)} \text{ gir største elementet i en liste med }n\text{ elementer.}$

8

Induksjon og algoritmer

Induksjonsbevis for at MAKS(LISTE) er korrekt

$\mathrm{P}(n) \coloneqq \hspace{1cm} \mathrm{MAKS(LISTE)} \text{ gir største elementet i en liste med }n\text{ elementer.}$

Grunntilfelle $\mathrm{P}(1)$

Største element i listen $[x]$ ? Må jo være $x$ !

Induktivt steg $\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$

Vi vil finne største element i en liste med $k$ elementer.
Induksjonshypotese: $\mathrm{MAKS(LISTE)}$ kan finne største element i en liste med $k-1$ elementer.
Dette kan være de første $k-1$ elementene i listen vår.

1

2

3

...

k-3

k-2

k-1

k

$\mathrm{MAKS}(\mathrm{LISTE}[1:k-1])$

$\mathrm{LISTE}[k]$

9

Induksjon og algoritmer

Implementasjon av MAKS(LISTE)

def maks(liste):
    if len(liste) == 1:
        return liste[0]
        
    delinstans = liste[0:-1] # Hele listen unntatt siste element
    delløsning = maks(delinstans)
    
    if delløsning > liste[-1]:
        return delløsning
    else:
        return liste[-1]
def maks(liste):
    if len(liste) == 1:
        return liste[0]
        
    delinstans = liste[0:-1] # Hele listen unntatt siste element
    delløsning = maks(delinstans)
    
    if delløsning > liste[-1]:
        return delløsning
    else:
        return liste[-1]

5

3

7

6

8

3

10

Hetlands stige igjen

Denne gangen for delinstanser

11

Iterasjon

MAKS(LISTE) med konstant minnebruk!

def maks(liste):
    storst = float("-inf")
    for tall in liste:
        if tall > storst:
            storst = tall
    return storst
def maks(liste):
    storst = float("-inf")
    for tall in liste:
        if tall > storst:
            storst = tall
    return storst

12

Iterasjon

Hvordan formalisere dette?

Iterasjonsinvariant: etter $k$ iterasjoner inneholder $storst$ det største av de første $k$ tallene.
Vi må bevise at dette stemmer før og etter hver iterasjon.

13

Kjøretidsanalyse med rekkurenser

Hvor mye jobb gjør rekursjonen?

Et kall til $\mathrm{MAKS}(\mathrm{LISTE})$ gjør:

ett kall til $\mathrm{MAKS}$ med en hakket mindre liste
én sammenligning med bakerste element

Hvis $\mathrm{LISTE}$ bare har ett element:

returnerer tallet

$\begin{align*} T(1) &= 1 \\ T(n) &= T(n-1) + 1 \end{align*}$

14

Rekursenser med Iterasjonsmetoden

Fra eksamen August 2021

15

Verifisering ved substitusjon

Dette er i praksis induksjon igjen

16

Masterteoremet

Fint nå én T(n) blir til mange

Vi har en rekkurens på formen

$\mathrm{T}(n) = a\mathrm{T}(n/b) + f(n)$

Avhengig av hvordan $f(n)$ ser ut får vi en av følgende:

$f(n)$	$\mathrm{T}(n)$
$\mathrm{O}(n^{\log_b a - \epsilon})$	$\Theta(n^{\log_b a})$
$\Theta(n^{\log_b a})$	$\Theta(n^{\log_b a} \cdot \log_b n)$
$\Omega(n^{\log_b a + \epsilon})$	$\Theta(f(n))$

17

Oppgave

Eksamen desember 2018

18

Asymptotisk notasjon

Vi bryr oss bare om hva som skjer når $n$ blir stor

Uttales "store O", "store Omega" og "store Theta"

$\mathrm{O}(g(n)) \text{ - mengden funksjoner som vokser }\leq c\cdot g(n)$

$\Omega(g(n)) \text{ - mengden funksjoner som vokser }\geq c\cdot g(n)$

$\Theta(g(n)) \equiv \mathrm{O}(g(n)) \cap \Omega(g(n))$

Syntaks

$n + 4 \log(n) = \mathrm{O}(n^2)$

19

Store O

En øvre grense

$\begin{align*} f(n) &= \mathrm{O}(g(n)) &\Leftrightarrow\ \ f(n) &\leq C \cdot g(n),\ \ \ \ \forall n\in[n_0,\infty) \end{align*}$

$\begin{align*} n &= \mathrm{O}(n^2) \\ 3n^2 &= \mathrm{O}(n^2) \\ 3n^2 + n + 4 &= \mathrm{O}(n^2) \end{align*}$

Forkast konstanter og mindre ledd!

20

Alternativ definisjon

Grenseverdier anyone?

$f(n) = \mathrm{O}(g(n))\ \ \ \Leftrightarrow\ \ \ \lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} < \infty$

Grenseverdien er en "kamp" mellom teller og nevner.

Hvis $f(n)$ går raskest mot $\infty$ vil brøken gå til $\infty$ .

Hvis $g(n)$ går raskest mot $\infty$ vil brøken gå mot $0$ .

Hvis de er asymptotisk "like" vil brøken konvergere mot et tall $C > 0$ .

21

De andre symbolene

Også viktige!

$f(n)=\mathrm{O}(g(n))$	$g(n)=\mathrm{O}(f(n))$	Ekvivalent med
Ja	Nei	$f(n)=\mathrm{o}(g(n))$
	Ja	$f(n)=\Omega(g(n))$
Nei	Ja	$f(n)=\omega(g(n))$
Ja	Ja	$f(n)=\Theta(g(n))$

22

Eksempel lille o

$\begin{align*} 1 &= \mathrm{o}(\log(n)) \\ \log(n) &= \mathrm{o}(\log^2(n)) \\ \log^k(n) &= \mathrm{o}(\sqrt{n}), \forall k \\ \sqrt{n} &= \mathrm{o}(n) \\ n &= \mathrm{o}(n \log n) \\ n \log n &= \mathrm{o}(n^2) \\ n^k &= \mathrm{o}(n^{k+\epsilon}),\ \forall k \\ n^k &= \mathrm{o}(a^n), \forall k,a \\ a^n &= \mathrm{o}(n!),\ \forall a \end{align*}$

$\begin{align*} 4n^2 + 3n \log n + 1000 n &= \mathrm{o}(n^2\sqrt{n}) \\ n^3 &= \mathrm{o}(n^4 + n^2 + n) \end{align*}$

23

Eksempel store O

Den populære storebroren

Hvis $f(n) = \mathrm{o}(g(n))$ , medfører det automatisk $f(n) = \mathrm{O}(g(n))$ .

$\begin{align*} 4n^3 + 5n^2 -10n +7 &= \mathrm{O}(n^3) \\ \frac{n(n-1)}{2} &= \mathrm{O}(n^2) \\ 4 n \log^2(n) + 5 \log^2(n) &= \mathrm{O}(n \log^2(n)) = \mathrm{O}(n^2) \end{align*}$

24

Eksempel lille $\omega$ og store $\Omega$

Motsatt av de forrige

Rett og slett bare det motsatte av henholdsvis $\mathrm{o}$ og $\mathrm{O}$ .

$\begin{align*} \text{hva som helst positivt} &= \Omega(1) \\ n^2 &= \Omega(n^2) \\ n^2 &= \Omega(n^2 + n) \\ n^2 + n &= \Omega(n^2) \\ n^6 &= \omega(n^2) \\ n^2 &= \omega(n \log(n)) \\ \end{align*}$

25

Eksempel $\Theta$

Når de er like

Hvis $f(n) = \mathrm{O}(g(n))$ og $f(n) = \Omega(g(n))$ , er de asymptotisk like.

$\Rightarrow f(n) = \Theta(g(n))$

$C_1 \cdot g(n)$ er en øvre grense, $C_2 \cdot g(n)$ er en nedre grense for $f(n)$ .

$\begin{align*} 3n^2 + 3n + \log n &= \Theta(n^2) \\ n^2 &= \Theta(3n^2 + 3n + \log n) \\ \log_2(n) &= \Theta(\log_10(n)) \end{align*}$

26

Ligninger med $\mathrm{o}, \mathrm{O}, \Theta, \Omega, \omega$

Attentat på notasjon

Når vi skriver disse symbolene på venstre side, betyr det noe nytt!

$\begin{align*} \mathrm{O}(n^2) + n &= \mathrm{O}(n^2) \\ \mathrm{O}(n^2) + n &= \mathrm{o}(n^3) \\ \mathrm{O}(n^2) + n &= \Omega(n) \\ \mathrm{O}(n^2) + n &= \mathrm{O}(n^2) + \Omega(n) \\ \mathrm{O}(n^2) + n &= \omega(1) \end{align*}$

Uansett hva vi setter inn på venstresiden, må det finnes noe å sette på høyresiden

27

Oppgave

Øving 1 oppgave 9

28

Oppgave

Øving 1 oppgave 10

29

Oppgave

Eksamen Desember 2017, 2b

30

Worst case vs Store O

De er ikke det samme!

$\mathrm{o}, \mathrm{O}, \Theta, \Omega, \omega$ er matematisk asymptotisk notasjon.

31

Datastrukturer

Vi går fort gjennom

Stakk
Kø
Lenket liste
Hash-tabell
Dynamisk tabell

32

Stakk

Først inn, sist ut

PUSH(elm)
POP()
STACK-EMPTY()
Alle i konstant tid: $\Theta(1)$

33

Kø

Først inn, først ut

ENQUEUE(elm)
- Legger element på $tail$ .
DEQUEUE(elm)
- Henter ut element på $head$ .
Begge er konstant tid: $\Theta(1)$

34

Lenket liste

Følg pekerne

LIST-SEARCH(elm)
- Finner første node med tallet $elm$ . $\mathrm{O}(n)$
LIST-INSERT(node)
- Setter node $node$ foran $head$ . Blir ny $head$ . $\Theta(1)$
LIST-DELETE(node)
- Sletter noden $node$ , tetter igjen gapet. $\Theta(1)$

35

Direkte adressering

Kobling mellom nøkkel og tabell-plassering

36

Hashtabell

Indirekte kobling mellom nøkkel og tabell-plassering

37

Hashtabell

Med kjeding av kollisjoner

INSERT(key, value)
- Setter inn, tar $\mathrm{O(j)}$
LOOKUP(key)
- Finner value for $key$ , tar $\mathrm{O(j)}$
DELETE(key)
- Fjerner for $key$ , tar $\mathrm{O(j)}$

38

Amortisert resizing

Så lenge det ikke skjer så ofte går det fint!

$j$ er lengden på den lengste kjeden.

Hvis $h(k)$ er god, er $j \simeq \frac{n}{m} (\cdot 2)$

Hvis vi øker $n$ slik at $j$ holdes under e.g. 10

Blir lookup $\mathrm{O}(j) = \mathrm{O}(1)$ .

Men! Det koster å resize! $\Theta(n + m)$

39

Amortisert resizing

Det samme gjelder for dynamiske tabeller

Vi ønsker en tabell som alltid har plass til mer.

Sett av plass til $n$ elementer.

De første $n$ TABLE-INSERT blir $\mathrm{O}(1)$ .

Når det er fullt, øk $n$ med en faktor 2. Dette koster $\mathrm{O}(2n) = \mathrm{O}(n)$ .

Til gjengjeld er det $n$ ARRAY-INSERT til neste gang.

TABLE-INSERT er amortisert $\mathrm{O}(1)$ .

40

Hash-tabell-oppgave

Eksamen desember 2018

41

Insertion sort

Funker fjell for små tabeller

Sorterer de første $k$ elementene i lista, fra $k=1$ opp til $k=n$ .

Gjør dette ved å swappe element $k$ ned dit den skal, for hver $k$ .

Best case: $\Theta(n)$

Worst case: $\Theta(n^2)$

Average case: $\Theta(n^2)$

42

Eksamensoppgave Insertion Sort

Eksamen august 2018

2 Hva er kjøretiden til INSERTION-SORT på en sortert tabell

43

Merge sort

Splitt og hersk!

Del listen i to. Løs hver delinstans for seg.

Flett sammen de to sorterte listene.

resultat = MERGE(liste1, liste2)

Best case: $\Theta(n \log n)$

Worst case: $\Theta(n \log n)$

Average case: $\Theta(n \log n)$

44

Eksamensoppgave Merge Sort

Eksamen august 2018

11 . Hvordan kan vi si at MERGE-SORT er optimal? Forklar.

45

Quick sort

Rask, men med en hake

Velg et element som $pivot$ .

Bruk PARTITION(liste, pivot). $\Theta(n)$

Dette deler lista inn i to deler, adskilt av $pivot$ .

$[a, b, c \ldots] \leq [pivot] \leq [x, y, z, \ldots]$

Nå vet vi at $pivot$ er på rett plass. Sorter hver av sidene for seg.

Hvis vi er heldige (som regel) er listen delt omtrent i 2.

$T(n) \simeq 2T(n/2) + n$

Vi er uheldige om vi velger en veldig høy eller lav pivot.

46

Randomized Quicksort

Kryss fingrene

Hindrer oss fra å ha "slemme" inputs.

QUICKSORT: alltid ta bakerste som pivot
- (En allerde sortert liste ville vært døden)
RANDOMIZED-QUICKSORT:
- Sannsynligheten for å få mange dårlige pivots er lav.

Best case: $\Theta(n \log n)$

Worst case: $\Theta(n^2)$

Forventet kjøretid: $\Theta(n \log n)$

Den er in-place!

47

Oversikt sammenligningsbasert sortering

Navn	Best case	Worst case	Average	In place?
Insertion sort	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	Ja!
Merge sort	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$	Nei
Quicksort	$\Theta(n \log n)$	$\Theta(n^2)$	$\Theta(n \log n)$ [1]	ja

[1]: Vi bruker ordet forventet, ikke gjennomsnittlig, når det er randomized

48

Oppgave om kjøretidsfunksjoner

Eksamen november 2020

49

Sortering i lineær tid

Bedre enn $\Theta(n \log n)$ sier du?

Hvis den eneste operasjonen vår er $(a < b)?$ , vil gjennomsnittlig kjøretid alltid være $\Omega(n \log n)$ .

50

Randomized Select

RANDOMIZED-SELECT

Det er mulig å finne det $k$ minste elementet på forventet $\Theta(n)$ tid.

Bruker PARTITION fra quicksort, men ser bare på én av resultatlistene.

Worst case fortsatt $\Theta(n^2)$ .

Finnes også SELECT, som har worst case $\Theta(n)$.

51

Counting sort

Kan telle hver mulige verdi for seg

Tabellen som skal sorteres har $k$ mulige verdier.

Vi kan lage en tabell av lengde $k$ for å telle forekomster av hver.

Etterpå bruker vi denne tabellen for å finne intervallene til hver verdi.

Vi kan gjøre stabil sortering

Kjøretid alltid $\Theta(n+k)$ .

52

Radix sort

Tallene våre har begrenset antall siffer

Sorter et siffer av gangen, for alle $d$ siffer.

Begynn med de minst signifikante sifferne.

Krever at hvert siffer sorteres stabilt.

Til gjengjeld har hvert siffer $k$ mulige verdier.

COUNTING-SORT fungerer altså utmerket!

Kjøretid $\Theta(d \cdot (n + k))$

53

Bøttesortering

Verdier uniformt fordelt

Fungerer bare når alle verdiene er uniformt fordelt i $[0, 1)$ .

For $n$ tall, del intervallet $[0,1)$ inn i $n$ bøtter.

Legg hvert tall i riktig bøtte.

Mange bøtter blir tomme, noen får flere tall.

Bruk lenka lister

Sorter hver bøtte for seg med INSERTION-SORT.

Veldig usannsynlig om en av bøttene har feks 10 elementer.

Hver bøtte-sortering blir derfor konstant tid $\mathrm{O}(1)$

Gjennomsnittlig kjøretid $\Theta(n)$ . Worst case $\Theta(n^2)$

54

Bøttesortering oppgave

Eksamen desember 2016

55

Rotfestede trær

Tegnet av folk som aldri har vært i skogen

På toppen har vi en rot.

roten har kanter new til barn-nodene sine.

Alle noder som ikke er rot har en forelder.

Noder uten barn kalles løvnoder.

Avstanden fra roten kalles dybde.

I et posisjonstre har hvert barn en posisjon i forelderen.

Et binæretre har to posisjoner per node. Venstre og høyre

56

Komplette binærtrær

Pent og symmetrisk

Når alle løvnodene i et binærtre er på samme dybde $h$ .

Antall løvnoder blir $2^h$ .

Antall interne noder blir $2^h - 1$

Antall noder totalt $n = 2^{h+1}-1$

57

Binære søketrær

Finn frem fort!

Venstre subtre har kun lavere verdier.

Høyre subtre har kun høyere verdier.

En INORDER-WALK gir tallene i stigende rekkefølge.

SEARCH(k) finner $k$ på $\mathrm{O}(\log n)$ tid.

Hvis treet er temmelig balansert

INSERT(k) setter inn noden $k$ på riktig sted. $\mathrm{O}(\log n)$ .

Flere trær kan være riktige!

58

Maks-hauger

Størst først

Et binærtre der alle interne noder er større enn barna sine.

Høyden er garantert $\Theta(\log n)$ .

MAX-HEAPIFY(i) - swapper verdien på plass $i$ nedover til den sitter.

Brukes når en verdi ligger for høyt. $\mathrm{O}(\log n)$

BUILD-MAX-HEAP(i) - gjør en vilkårlig liste med tall om til en heap.

Kjører MAX-HEAPIFY() på alle, likevel $\mathrm{O}(n)$

59

BUILD-MAX-HEAP er lineær?

Jeppsi

60

Prioritetskøer

Lurt å bruke en maks-haug

HEAP-EXTRACT-MAX() - henter ut det største tallet

Alltid på toppen, men så må vi finne en ny topp. $\mathrm{O}(\log n)$

HEAP-INCREASE-KEY(i, value) - øker verdien til node $i$

Swapper noden oppover til den sitter. $\mathrm{O}(\log n)$

MAX-HEAP-INSERT(value) - setter inn en ny node med $verdi$

Ny node settes alltid på bunnen, swappes så opp. $\mathrm{O}(\log n)$

61

Makshaug - oversikt

Kjekt å ha

62

Heap sort

Alltid plukk det største

Bruk BUILD-MAX_HEAP på listen med tall. $\Theta(n)$

Bruk HEAP-EXTRACT-MAX og sett maks bakerst. $n \cdot \mathrm{O}(\log n)$

Heapen blir mindre og mindre, til slutt er alt sortert.

Kjøretid: $\Theta(n \log n)$ . In-place!!

63

Krav til dynamisk programmering

Det er lov å kalle det DP!

Optimal delestruktur: Det finnes en optimal løsning bestående av delløsninger

Overlappende delproblemer: Vi er avhengig av samme delproblem flere ganger

Altså: Vi gjør rekursiv dekomponering akkurat som før, men noen delproblemer går igjen, så lagre resultatene til senere.

64

Dynamisk programmering

Eksamen november 2020

65

Krabbedans

Krabbemusikk har veldig rar rytme. Musikken er delt inn i $n$ strofer, der hver strofe har lengde $l_i$ slag ( $0 \leq i \le n$ ).

Når en strofe spiller, kan krabben enten gå til høyre eller venstre, eller stå stille.

Men: krabben må gå samme retning hele strofen. Én rute per slag i strofen.

Dansescenen er $k$ ruter bred. Krabben starter i rute $0$ .

Krabben har lyst til å bevege seg flest mulig av strofene. Krabben kan ikke bevege seg utenfor scenen. Hvordan blir dansen?

66

Midtsemester TDT4120

Algoritmer og Datastrukturer

Håvard Krogstie - høsten 2021

Induksjon

Grunntilfelle

Induktivt steg

Midtsemester TDT4120

Algoritmer og Datastrukturer

Håvard Krogstie - høsten 2021

Induksjon

Grunntilfelle

Induktivt steg

Induksjon - Hetlands stige

Induksjon Eksempel

Hvordan viser vi dette?

Induksjon Eksempel

Grunntilfelle

Induksjon Eksempel

Grunntilfelle P(0)\mathrm{P}(0)P(0) ✔

Induktivt steg

Induksjon Eksempel

Grunntilfelle P(0)\mathrm{P}(0)P(0) ✔

Induktivt steg P(k−1)⇒P(k)\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)P(k−1)⇒P(k) ✔

Induksjon og algoritmer

Induksjon og algoritmer

Grunntilfelle P(1)\mathrm{P}(1)P(1)

Induktivt steg P(k−1)⇒P(k)\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)P(k−1)⇒P(k)

Induksjon og algoritmer

Hetlands stige igjen

Iterasjon

Iterasjon

Kjøretidsanalyse med rekkurenser

Rekursenser med Iterasjonsmetoden

Verifisering ved substitusjon

Masterteoremet

Oppgave

Asymptotisk notasjon

Syntaks

Store O

Alternativ definisjon

De andre symbolene

Eksempel lille o

Eksempel store O

Eksempel lille ω\omegaω og store Ω\OmegaΩ

Eksempel Θ\ThetaΘ

Ligninger med o,O,Θ,Ω,ω\mathrm{o}, \mathrm{O}, \Theta, \Omega, \omegao,O,Θ,Ω,ω

Oppgave

Oppgave

Oppgave

Worst case vs Store O

Datastrukturer

Stakk

Kø

Lenket liste

Direkte adressering

Hashtabell

Hashtabell

Amortisert resizing

Amortisert resizing

Hash-tabell-oppgave

Insertion sort

Eksamensoppgave Insertion Sort

Merge sort

Eksamensoppgave Merge Sort

Quick sort

Randomized Quicksort

Oversikt sammenligningsbasert sortering

Oppgave om kjøretidsfunksjoner

Sortering i lineær tid

Randomized Select

Counting sort

Radix sort

Bøttesortering

Bøttesortering oppgave

Rotfestede trær

Komplette binærtrær

Binære søketrær

Maks-hauger

BUILD-MAX-HEAP er lineær?

Prioritetskøer

Grunntilfelle $\mathrm{P}(0)$ ✔

Grunntilfelle $\mathrm{P}(0)$ ✔

Induktivt steg $\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$ ✔

Grunntilfelle $\mathrm{P}(1)$

Induktivt steg $\mathrm{P}(k-1) \Rightarrow \mathrm{P}(k)$

Eksempel lille $\omega$ og store $\Omega$

Eksempel $\Theta$

Ligninger med $\mathrm{o}, \mathrm{O}, \Theta, \Omega, \omega$