3.3 Rekursjon og dynamisk programmering

Datastrukturar

Ein datastruktur er ein måte å organisere og lagre data på, slik at vi kan bruke dei effektivt. Val av rett datastruktur kan utgjere enorm forskjell for både yting og lesbarheit i koden din.

I dette kapittelet skal du lære:
- Kva ein datastruktur er og kvifor det er viktig
- Lister og operasjonane deira
- Stakkar (LIFO) og køar (FIFO)
- Ordbøker (dictionaries) og oppslag
- Mengder (sets) og mengdeoperasjonar
- Korleis du vel rett datastruktur

Alle eksempla bruker Pythons innebygde datastrukturar, som er godt optimaliserte og enkle å bruke.

Kvifor er datastrukturar viktige?

Tenk på det som forskjellen mellom å leite etter eit ord i ein usortert bunke med lappar, versus å slå opp i ei ordbok. Begge inneheld dei same orda, men organiseringa gjer ein enorm forskjell.

Viktige eigenskapar å vurdere:

Lister er den mest brukte datastrukturen i Python. Dei er fleksible og støttar mange operasjonar.

Grunnleggjande operasjonar:

# 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

Tidskompleksitetar for lister:

Gitt denne koden:

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

Kva inneheld data etter at alle operasjonane er utførte?

Analogi: Tenk på ein stabel med tallerkenar. Du legg alltid ein ny tallerken på toppen, og tek alltid den øvste tallerkenen først.

Operasjonar:
- push(element): Legg til element på toppen
- pop(): Fjern og returner element frå toppen
- peek(): Sjå på toppelementet utan å fjerne det
- is_empty(): Sjekk om stakken er tom

Alle operasjonar er O(1)!

Bruksområde:
- Angre-funksjonar (Ctrl+Z)
- Navigasjonshistorikk i nettlesarar
- Funksjonskall-stakken (call stack)
- Evaluering av parentesar og uttrykk
- Djupne-først-søk (DFS)

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

Python har inga eiga stakk-klasse, men lister fungerer utmerkt som stakkar:

Grunnleggjande 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

Korleis 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ølgjande operasjonar på ein tom stakk:

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

Kva er igjen i stakken?

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

Operasjonar:
- enqueue(element): Legg til element bakarst
- dequeue(): Fjern og returner element frå fronten
- front(): Sjå på frontelementet utan å fjerne det
- is_empty(): Sjekk om køen er tom

Bruksområde:
- Køsystem (print-kø, ventekø)
- Breidde-først-søk (BFS)
- Asynkrone oppgåver (task queue)
- Bufferar (t.d. tastaturinput)

I Python: Bruk collections.deque i staden for vanleg liste for køar, fordi deque har O(1) for både innsetting bak og fjerning framme.

Kvifor ikkje vanleg liste?
- liste.pop(0) er O(n) - må flytte alle element
- deque.popleft() er O(1) - effektivt begge vegar

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!

Samanlikning: list vs deque

For kvart scenario, avgjer om du bør bruke ein stakk (LIFO) eller ein kø (FIFO):

A) Angre-funksjon i eit tekstprogram
B) Skrivekø for ein printar
C) Tilbake-knappen i ein nettlesar
D) Behandle kundehenvendingar i den rekkjefølgja dei kom inn

Eigenskapar:
- Nøklar må vere unike og uforanderlege (str, int, tuple)
- Verdiar kan vere kva som helst
- Rekkjefølgje blir bevart (frå Python 3.7+)
- Oppslag, innsetting og sletting er O(1) i gjennomsnitt

Tidskompleksitetar:

- Caching / memoisering
- Konfigurasjonsinnstillingar

# 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}")

Enklare 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 elevar og ofte slå opp ein elev basert på elevnummeret.

Kva for ein datastruktur er best?

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

Eigenskapar:
- Ingen duplikat
- Uordna (inga indeksering)
- Element må vere uforanderlege (hashable)
- Raske medlemskapstestar: O(1)

Tidskompleksitetar:

- Rask sjekk av medlemskap
- Finne felles eller unike element mellom samlingar
- 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}

Kva er resultatet av A & B?

- Ja, og du legg til/fjernar mest i endane -> deque

- Ja, generell bruk -> list
Ytingssamanlikning 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 byggje eit system for å administrere ein nettbutikk. Vel rett datastruktur for kvart behov:

A) Lagre produktinformasjon der kvart produkt har ein unik ID
B) Halde styr på handlekorga (ordna liste av produkt)
C) Halde styr på kva for produkt ein kunde har sett (ingen duplikat)
D) Implementere ein "sist sett"-funksjon der nyaste produkt blir vist først

Oppsummering

Datastrukturar i Python:

2. Treng du ordna sekvens? -> list eller deque

3. Treng du unike element? -> set
4. Treng du nøkkel-verdi? -> dict
Ytingstips:

- Bruk set for medlemskapstestar, ikkje list
- Bruk deque for køar, ikkje list
- Bruk dict for oppslag, ikkje nesta løkker
- Vel rett datastruktur FØR du byrjar å kode

Samleoppgåver

Oppgåver som kombinerer fleire datastrukturar:

Du skal lage eit enkelt inventarsystem for ein butikk. Systemet skal kunne:
- Leggje til produkt med namn og tal
- Oppdatere talet for eksisterande produkt
- Fjerne produkt som er utselde
- Finne produkt raskt basert på namn

Kva for ein datastruktur eignar seg best, og korleis ville du implementert det?

Sjå på desse to implementasjonane som sjekkar om to lister har felles element:

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