3.3 Rekursjon og dynamisk programmering

Datastrukturer

En datastruktur er en måte å organisere og lagre data på, slik at vi kan bruke dem effektivt. Valg av riktig datastruktur kan utgjøre enorm forskjell for både ytelse og lesbarhet i koden din.

I dette kapittelet skal du lære:
- Hva en datastruktur er og hvorfor det er viktig
- Lister og deres operasjoner
- Stakker (LIFO) og køer (FIFO)
- Ordbøker (dictionaries) og oppslag
- Mengder (sets) og mengdeoperasjoner
- Hvordan du velger riktig datastruktur

Alle eksemplene bruker Pythons innebygde datastrukturer, som er godt optimalisert og enkle å bruke.

Hvorfor er datastrukturer viktige?

Tenk på det som forskjellen mellom å lete etter et ord i en usortert bunke med lapper, versus å slå opp i en ordbok. Begge inneholder de samme ordene, men organiseringen gjør en enorm forskjell.

Viktige egenskaper å vurdere:

Lister er den mest brukte datastrukturen i Python. De er fleksible og støtter mange operasjoner.

Grunnleggende operasjoner:

# Opprette lister
tall = [1, 2, 3, 4, 5]
tomme = []
blandet = [1, "hei", True, 3.14]

# Tilgang med indeks - O(1)
print(tall[0])    # 1 (første element)
print(tall[-1])   # 5 (siste element)

# Slicing - O(k) hvor k er størrelsen på utsnitt
print(tall[1:3])  # [2, 3]
print(tall[::2])  # [1, 3, 5] (annethvert element)

# Legge til elementer
tall.append(6)         # O(1) - legger til på slutten
tall.insert(0, 0)      # O(n) - skyver alle elementer
tall.extend([7, 8])    # O(k) - legger til flere

# Fjerne elementer
tall.pop()             # O(1) - fjerner siste
tall.pop(0)            # O(n) - fjerner første, skyver resten
tall.remove(3)         # O(n) - søker og fjerner

# Søking
indeks = tall.index(4)    # O(n) - finn indeks
finnes = 4 in tall         # O(n) - sjekk om element finnes

# Lengde
print(len(tall))           # O(1) - returnerer lengden

Tidskompleksiteter for lister:

Gitt denne koden:

data = [10, 20, 30, 40, 50]
data.append(60)
data.insert(0, 5)
data.pop()
data.pop(0)

Hva inneholder data etter at alle operasjonene er utført?

Analogi: Tenk på en stabel med tallerkener. Du legger alltid en ny tallerken på toppen, og tar alltid den øverste tallerkenen først.

Operasjoner:
- push(element): Legg til element på toppen
- pop(): Fjern og returner element fra toppen
- peek(): Se på toppelementet uten å fjerne det
- is_empty(): Sjekk om stakken er tom

Alle operasjoner er O(1)!

Bruksområder:
- Angre-funksjoner (Ctrl+Z)
- Navigasjonshistorikk i nettlesere
- Funksjonskall-stakken (call stack)
- Evaluering av parenteser og uttrykk
- Dybde-først-søk (DFS)

I Python: Vi bruker en vanlig liste som stakk - append() for push og pop() for pop.

Python har ingen egen stakk-klasse, men lister fungerer utmerket som stakker:

Grunnleggende bruk:

# Stakk med vanlig liste
stakk = []

# Push - legg til på toppen
stakk.append("A")
stakk.append("B")
stakk.append("C")
print(stakk)  # ['A', 'B', 'C']

# Peek - se på toppen
print(stakk[-1])  # 'C'

# Pop - fjern fra toppen
topp = stakk.pop()
print(topp)    # 'C'
print(stakk)   # ['A', 'B']

# Sjekk om tom
print(len(stakk) == 0)  # False

Praktisk eksempel: Sjekke balanserte parenteser

def er_balansert(tekst):
    """
    Sjekker om parenteser, klammer og krøllparenteser er balansert.
    Bruker en stakk til å holde styr på åpne parenteser.
    """
    stakk = []
    par = {"(": ")", "[": "]", "{": "}"}

    for tegn in tekst:
        if tegn in par:
            # Åpen parentes - push på stakken
            stakk.append(tegn)
        elif tegn in par.values():
            # Lukket parentes - sjekk mot toppen
            if not stakk:
                return False  # Ingen åpen parentes å matche
            åpen = stakk.pop()
            if par[åpen] != tegn:
                return False  # Feil type parentes

    # Stakken skal være tom hvis alt er balansert
    return len(stakk) == 0

# Test
print(er_balansert("(a + b) * [c - d]"))     # True
print(er_balansert("((a + b)"))                # False - mangler )
print(er_balansert("{[}]"))                    # False - feil rekkefølge
print(er_balansert("hello world"))             # True - ingen parenteser

Hvordan stakken fungerer for (a + [b]):

Tegn: (    stakk: ['(']
Tegn: a    stakk: ['(']        (ignorert)
Tegn: +    stakk: ['(']        (ignorert)
Tegn: [    stakk: ['(', '[']
Tegn: b    stakk: ['(', '[']   (ignorert)
Tegn: ]    stakk: ['(']        (matchet med '[')
Tegn: )    stakk: []           (matchet med '(')
Ferdig: stakk er tom -> balansert!

Du utfører følgende operasjoner på en tom stakk:

stakk = []
stakk.append(1)
stakk.append(2)
stakk.append(3)
stakk.pop()
stakk.append(4)
stakk.pop()
stakk.pop()

Hva er igjen i stakken?

Analogi: Tenk på en kø i butikken. Den som kom først, blir betjent først.

Operasjoner:
- enqueue(element): Legg til element bakerst
- dequeue(): Fjern og returner element fra fronten
- front(): Se på frontelementet uten å fjerne det
- is_empty(): Sjekk om køen er tom

Bruksområder:
- Køsystemer (print-kø, ventekø)
- Bredde-først-søk (BFS)
- Asynkrone oppgaver (task queue)
- Buffere (f.eks. tastaturinput)

I Python: Bruk collections.deque i stedet for vanlig liste for køer, fordi deque har O(1) for både innsetting bak og fjerning foran.

Hvorfor ikke vanlig liste?
- liste.pop(0) er O(n) - må flytte alle elementer
- deque.popleft() er O(1) - effektivt begge veier

from collections import deque

# Opprett en kø
kø = deque()

# Enqueue - legg til bakerst
kø.append("Kunde 1")
kø.append("Kunde 2")
kø.append("Kunde 3")
print(kø)  # deque(['Kunde 1', 'Kunde 2', 'Kunde 3'])

# Dequeue - fjern fra fronten
neste = kø.popleft()
print(neste)  # 'Kunde 1'
print(kø)     # deque(['Kunde 2', 'Kunde 3'])

# Front - se på første element
print(kø[0])  # 'Kunde 2'

# Sjekk om tom
print(len(kø) == 0)  # False

Praktisk eksempel: Enkel oppgavekø

from collections import deque

def oppgavekø_demo():
    """Simulerer en enkel oppgavekø"""
    kø = deque()

    # Legg til oppgaver
    oppgaver = ["Skriv rapport", "Send e-post", "Les artikkel", "Oppdater kode"]
    for oppgave in oppgaver:
        kø.append(oppgave)
        print(f"Lagt til: {oppgave}")

    print(f"\nOppgaver i kø: {len(kø)}")

    # Behandle oppgaver i rekkefølge
    while kø:
        oppgave = kø.popleft()
        print(f"Utfører: {oppgave}")

    print("Alle oppgaver utført!")

oppgavekø_demo()

Output:

Lagt til: Skriv rapport
Lagt til: Send e-post
Lagt til: Les artikkel
Lagt til: Oppdater kode

Oppgaver i kø: 4
Utfører: Skriv rapport
Utfører: Send e-post
Utfører: Les artikkel
Utfører: Oppdater kode
Alle oppgaver utført!

Sammenligning: list vs deque

For hvert scenario, avgjør om du bør bruke en stakk (LIFO) eller en kø (FIFO):

A) Angre-funksjon i et tekstprogram
B) Skrivekø for en printer
C) Tilbake-knappen i en nettleser
D) Behandle kundehenvendelser i den rekkefølgen de kom inn

Egenskaper:
- Nøkler må være unike og uforanderlige (str, int, tuple)
- Verdier kan være hva som helst
- Rekkefølge bevares (fra Python 3.7+)
- Oppslag, innsetting og sletting er O(1) i gjennomsnitt

Tidskompleksiteter:

- Caching / memoisering
- Konfigurasjonsinnstillinger

# Opprette ordbok
elev = {
    "navn": "Emma",
    "alder": 17,
    "klasse": "3A",
    "karakterer": [5, 4, 6, 5]
}

# Oppslag - O(1)
print(elev["navn"])          # 'Emma'
print(elev.get("alder"))     # 17
print(elev.get("hobby", "Ukjent"))  # 'Ukjent' (standardverdi)

# Sett inn / oppdater - O(1)
elev["skole"] = "Katta VGS"
elev["alder"] = 18

# Sletting - O(1)
del elev["klasse"]

# Sjekk om nøkkel finnes - O(1)
print("navn" in elev)  # True

Praktisk eksempel: Telle ordfrekvens

def tell_ord(tekst):
    """Teller forekomster av hvert ord i en tekst"""
    ordtelling = {}
    ord_liste = tekst.lower().split()

    for ord in ord_liste:
        # Fjern tegnsetting
        ord = ord.strip(".,!?;:")
        if ord in ordtelling:
            ordtelling[ord] += 1
        else:
            ordtelling[ord] = 1

    return ordtelling

tekst = "Python er gøy. Python er kraftig. Python er Python."
resultat = tell_ord(tekst)
print(resultat)
# {'python': 4, 'er': 3, 'gøy': 1, 'kraftig': 1}

# Sorter etter frekvens
sortert = sorted(resultat.items(), key=lambda x: x[1], reverse=True)
for ord, antall in sortert:
    print(f"{ord}: {antall}")

Enklere med Counter:

from collections import Counter

tekst = "Python er gøy. Python er kraftig. Python er Python."
ord_liste = tekst.lower().replace(".", "").split()
teller = Counter(ord_liste)
print(teller.most_common(3))
# [('python', 4), ('er', 3), ('gøy', 1)]

Du skal lagre informasjon om 10,000 elever og ofte slå opp en elev basert på elevnummeret.

Hvilken datastruktur er best?

A) En liste med elevnummer som indeks
B) En ordbok med elevnummer som nøkkel
C) En sortert liste som du søker i med binærsøk

Egenskaper:
- Ingen duplikater
- Uordnet (ingen indeksering)
- Elementer må være uforanderlige (hashable)
- Raske medlemskapstester: O(1)

Tidskompleksiteter:

- Rask sjekk av medlemskap
- Finne felles eller unike elementer mellom samlinger
- Filtrering

# Opprette mengder
frukt = {"eple", "banan", "kiwi"}
tall = {1, 2, 3, 2, 1}  # Duplikater fjernes
print(tall)  # {1, 2, 3}

# Fjerne duplikater fra en liste
liste_med_duplikater = [1, 2, 2, 3, 3, 3, 4]
unik_liste = list(set(liste_med_duplikater))
print(unik_liste)  # [1, 2, 3, 4]

# Medlemskapstester - O(1)
print("eple" in frukt)   # True
print("mango" in frukt)  # False

Mengdeoperasjoner:

fag_anna = {"matte", "norsk", "engelsk", "naturfag"}
fag_bob = {"matte", "norsk", "historie", "gym"}

# Union - alle fag samlet
alle_fag = fag_anna | fag_bob
print(alle_fag)
# {'matte', 'norsk', 'engelsk', 'naturfag', 'historie', 'gym'}

# Snitt - felles fag
felles = fag_anna & fag_bob
print(felles)  # {'matte', 'norsk'}

# Differanse - fag bare Anna har
bare_anna = fag_anna - fag_bob
print(bare_anna)  # {'engelsk', 'naturfag'}

# Symmetrisk differanse - fag bare én av dem har
ulike = fag_anna ^ fag_bob
print(ulike)  # {'engelsk', 'naturfag', 'historie', 'gym'}

Praktisk eksempel: Finn felles venner

venner = {
    "Anna": {"Bob", "Charlie", "Diana", "Eva"},
    "Bob": {"Anna", "Charlie", "Frank"},
    "Charlie": {"Anna", "Bob", "Diana"}
}

def felles_venner(person1, person2):
    """Finner felles venner mellom to personer"""
    v1 = venner.get(person1, set())
    v2 = venner.get(person2, set())
    felles = v1 & v2 - {person1, person2}
    return felles

print(felles_venner("Anna", "Bob"))
# {'Charlie'}

Gitt:

A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

Hva er resultatet av A & B?

- Ja, og du legger til/fjerner mest i endene -> deque

- Ja, generell bruk -> list
Ytelsessammenligning for x in samling:

import time

data_list = list(range(1_000_000))
data_set = set(range(1_000_000))
data_dict = {i: True for i in range(1_000_000)}

# Søk etter verdi som ikke finnes
# list:  ~50 ms    (O(n) - må sjekke alle)
# set:   ~0.001 ms (O(1) - hash-oppslag)
# dict:  ~0.001 ms (O(1) - hash-oppslag)

Du skal bygge et system for å administrere en nettbutikk. Velg riktig datastruktur for hvert behov:

A) Lagre produktinformasjon der hvert produkt har en unik ID
B) Holde styr på handlekurven (ordnet liste av produkter)
C) Holde styr på hvilke produkter en kunde har sett (ingen duplikater)
D) Implementere en "sist sett"-funksjon der nyeste produkt vises først

Oppsummering

Datastrukturer i Python:

2. Trenger du ordnet sekvens? -> list eller deque

3. Trenger du unike elementer? -> set
4. Trenger du nøkkel-verdi? -> dict
Ytelsestips:

- Bruk set for medlemskapstester, ikke list
- Bruk deque for køer, ikke list
- Bruk dict for oppslag, ikke nestede løkker
- Velg riktig datastruktur FØR du begynner å kode

Samleoppgaver

Oppgaver som kombinerer flere datastrukturer:

Du skal lage et enkelt inventarsystem for en butikk. Systemet skal kunne:
- Legge til produkter med navn og antall
- Oppdatere antallet for eksisterende produkter
- Fjerne produkter som er utsolgt
- Finne produkter raskt basert på navn

Hvilken datastruktur egner seg best, og hvordan ville du implementert det?

Se på disse to implementasjonene som sjekker om to lister har felles elementer:

Versjon A:

def felles_v1(liste1, liste2):
    for element in liste1:
        if element in liste2:
            return True
    return False

Versjon B:

def felles_v2(liste1, liste2):
    sett = set(liste2)
    for element in liste1:
        if element in sett:
            return True
    return False