3.1 Algoritmisk tenkning og effektivitet

Algoritmisk tenking og effektivitet

Når du programmerer, finst det ofte mange måtar å løyse same problem på. Men ikkje alle løysingar er like gode. Nokre program køyrer raskt sjølv med store datamengder, medan andre heng seg opp når dataene veks.

I dette kapittelet skal du lære å:
- Tenkje algoritmisk og strukturere løysingar
- Analysere kor effektiv ein algoritme er
- Forstå Big O-notasjon
- Optimalisere koden din for betre yting

Dette er grunnleggjande ferdigheiter for alle som jobbar med programmering og store datasett.

Ein god algoritme har desse eigenskapane:
- Definert input: Vi veit kva som går inn
- Definert output: Vi veit kva som skal ut
- Utvetydig: Kvart steg er klart definert
- Endeleg: Algoritmen stoppar etter eit visst tal steg
- Effektiv: Han løyser problemet på ein fornuftig måte

Døme på ein enkel algoritme for å finne det største talet i ei liste:
1. Start med første tal som "størst så langt"
2. Gå gjennom resten av lista
3. Viss du finn eit større tal, oppdater "størst så langt"
4. Når lista er ferdig, returner "størst så langt"

Lat oss sjå på to måtar å sjekke om ei liste har duplikat:

Løysing 1: Samanlikne kvart element med alle andre

def har_duplikater_v1(liste):
    """Sjekker om liste har duplikater - treg versjon"""
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                return True
    return False

# Test
tall = [1, 2, 3, 4, 5, 2]
print(har_duplikater_v1(tall))  # True

Løysing 2: Bruke eit sett (set)

def har_duplikater_v2(liste):
    """Sjekker om liste har duplikater - rask versjon"""
    return len(liste) != len(set(liste))

# Test
tall = [1, 2, 3, 4, 5, 2]
print(har_duplikater_v2(tall))  # True

Begge løysingane gjev rett svar, men løysing 2 er mykje raskare når lista er stor. Kvifor? Det handlar om kor mange operasjonar som må utførast.

Big O-notasjon: Ein matematisk måte å beskrive korleis køyretida veks når input blir større. Vi fokuserer på den dominerande faktoren og ignorerer konstantar.

Vanlege tidskompleksitetar (frå best til verst):

Lat oss analysere tidskompleksiteten til duplikat-funksjonane våre:

Løysing 1: Nøsta løkker

def har_duplikater_v1(liste):
    for i in range(len(liste)):          # n ganger
        for j in range(i + 1, len(liste)):  # opptil n ganger
            if liste[i] == liste[j]:     # Konstant tid
                return True
    return False

- Ytre løkke: n iterasjonar
- Indre løkke: opptil n iterasjonar
- Totalt: omtrent n × n = n² samanlikningar
- Tidskompleksitet: O(n²)

Løysing 2: Bruke set

def har_duplikater_v2(liste):
    return len(liste) != len(set(liste))

- set(liste): går gjennom lista éin gong (n operasjonar)
- len(): konstant tid for begge kall
- Tidskompleksitet: O(n)

Skilnaden i praksis:
- Med 100 element: O(n²) = 10,000 operasjonar vs O(n) = 100 operasjonar
- Med 1,000 element: O(n²) = 1,000,000 operasjonar vs O(n) = 1,000 operasjonar
- Med 10,000 element: O(n²) = 100,000,000 operasjonar vs O(n) = 10,000 operasjonar

Dette er grunnen til at tidskompleksitet betyr noko!

Kva er tidskompleksiteten til denne funksjonen?

def summer_alle(liste):
    total = 0
    for tall in liste:
        total += tall
    return total

To funksjonar finn om eit tal finst i ei liste:

# Funksjon A
def finn_v1(liste, mål):
    for element in liste:
        if element == mål:
            return True
    return False

# Funksjon B
def finn_v2(sortert_liste, mål):
    venstre = 0
    høyre = len(sortert_liste) - 1
    while venstre <= høyre:
        midten = (venstre + høyre) // 2
        if sortert_liste[midten] == mål:
            return True
        elif sortert_liste[midten] < mål:
            venstre = midten + 1
        else:
            høyre = midten - 1
    return False

Akkurat som tidskompleksitet brukar vi Big O-notasjon for plasskompleksitet.

Døme:

O(1) - Konstant plass:

def summer_alle(liste):
    total = 0  # Én variabel uansett liste-størrelse
    for tall in liste:
        total += tall
    return total

O(n) - Lineær plass:

def doble_alle(liste):
    ny_liste = []  # Ny liste med samme størrelse som input
    for tall in liste:
        ny_liste.append(tall * 2)
    return ny_liste

Viktig: Vi må ofte velje mellom tid og plass. Nokre gonger kan vi bruke meir minne for å få raskare køyretid (caching/memoisering).

Lat oss sjå på tre implementasjonar av Fibonacci-tala og effektiviteten deira:

Versjon 1: Naiv rekursjon

def fibonacci_v1(n):
    """Treg: O(2^n) tid, O(n) plass"""
    if n <= 1:
        return n
    return fibonacci_v1(n-1) + fibonacci_v1(n-2)

# Veldig treg for store tall!
print(fibonacci_v1(35))  # Tar flere sekunder

Versjon 2: Memoisering (caching)

def fibonacci_v2(n, cache={}):
    """Rask: O(n) tid, O(n) plass"""
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci_v2(n-1, cache) + fibonacci_v2(n-2, cache)
    return cache[n]

print(fibonacci_v2(35))  # Nesten øyeblikkelig

Versjon 3: Iterativ (best)

def fibonacci_v3(n):
    """Raskest: O(n) tid, O(1) plass"""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print(fibonacci_v3(35))  # Nesten øyeblikkelig

Samanlikning:
- V1: Eksponentiell tid, kan ikkje handtere store tal
- V2: Lineær tid, brukar ekstra minne for cache
- V3: Lineær tid, minimal minnebruk - beste løysinga!

Sjå på denne funksjonen:

def reverser_liste(liste):
    ny_liste = []
    for i in range(len(liste) - 1, -1, -1):
        ny_liste.append(liste[i])
    return ny_liste

Donald Knuth sa berømt: "Premature optimization is the root of all evil" (i programmering).

Retningslinjer for optimalisering:

1. Få det til å verke først: Skriv kode som løyser problemet korrekt
2. Mål ytinga: Bruk profileringsverktøy for å finne flaskehalsar
3. Optimaliser der det trengst: Fokuser på dei delane som faktisk er trege
4. Test at det framleis verkar: Verifiser at optimaliseringa ikkje introduserer bugs

Når bør du tenkje på effektivitet?
- Når du jobbar med store datasett (tusenvis eller millionar av element)
- I funksjonar som blir kalla veldig mange gonger
- Når brukarane opplever treg respons

Når er det mindre viktig?
- For små datasett (under 100 element)
- Kode som berre køyrer éin gong
- Når lesbarheit er viktigare enn fart

Hugseregel: Skriv lesbar kode først. Optimaliser seinare viss nødvendig.

Python har ein innebygd modul for å måle kor lang tid kode tek:

import timeit

# Lag testdata
store_data = list(range(10000))

# Test løsning 1
tid_v1 = timeit.timeit(
    lambda: har_duplikater_v1(store_data),
    number=10
)

# Test løsning 2
tid_v2 = timeit.timeit(
    lambda: har_duplikater_v2(store_data),
    number=10
)

print(f"Løsning 1: {tid_v1:.4f} sekunder")
print(f"Løsning 2: {tid_v2:.4f} sekunder")
print(f"Løsning 2 er {tid_v1/tid_v2:.1f}x raskere")

Output:

Løsning 1: 8.2450 sekunder
Løsning 2: 0.0023 sekunder
Løsning 2 er 3585.7x raskere

Dette viser konkret korleis skilnaden mellom O(n²) og O(n) påverkar køyretida!

Du har denne funksjonen som tel kor mange gonger kvart ord førekjem:

def tell_ord(tekst):
    ord_liste = tekst.lower().split()
    antall = []
    for ord in ord_liste:
        funnet = False
        for i in range(len(antall)):
            if antall[i][0] == ord:
                antall[i] = (ord, antall[i][1] + 1)
                funnet = True
                break
        if not funnet:
            antall.append((ord, 1))
    return antall

Kva er eit betre alternativ?

Sjå på denne funksjonen som sjekkar om ei liste er sortert:

def er_sortert(liste):
    for i in range(len(liste) - 1):
        if liste[i] > liste[i + 1]:
            return False
    return True

Oppsummering

I dette kapittelet har du lært:

Algoritmisk tenking:
- Ein algoritme er ei steg-for-steg-løysing på eit problem
- Same problem kan løysast på mange måtar med ulik effektivitet

Big O-notasjon:
- O(1): Konstant tid - best
- O(log n): Logaritmisk tid - veldig bra
- O(n): Lineær tid - akseptabelt
- O(n log n): Linearitmisk - bra for sortering
- O(n²): Kvadratisk tid - unngå viss mogleg
- O(2ⁿ): Eksponentiell tid - berre for små input

Tidskompleksitet:
- Beskriv kor mange operasjonar som krevst
- Fokuserer på worst-case-scenario
- Ignorerer konstante faktorar

Plasskompleksitet:
- Beskriv kor mykje minne som blir brukt
- Ofte trade-off mellom tid og plass

Optimalisering:
- Få koden til å verke først
- Mål ytinga før du optimaliserer
- Fokuser på flaskehalsar
- Ikkje optimaliser for tidleg

Praktiske tips:
- Unngå nøsta løkker over same data når mogleg
- Bruk innebygde datastrukturar (dict, set) for raske oppslag
- Bruk list comprehensions og generator expressions
- Test med realistiske datastorleikar

Samleoppgåver

Her er nokre oppgåver som kombinerer fleire konsept frå kapittelet:

Analyser tidskompleksiteten til denne funksjonen:

def finn_duplikat_par(liste):
    resultat = []
    for i in range(len(liste)):
        for j in range(i + 1, len(liste)):
            if liste[i] == liste[j]:
                resultat.append((i, j))
    return resultat

Du skal lage ein funksjon som finn dei 3 største tala i ei stor liste med millionar av tal.

Kva for ei tilnærming gjev best yting?

A) Sorter heile lista og ta dei tre siste
B) Gå gjennom lista éin gong og hald styr på dei tre største
C) Bruk Pythons heapq.nlargest()
D) Bruk max() tre gonger og fjern elementet kvar gong

Du har skrive denne koden for å finne alle anagram-par i ei liste med ord:

def finn_anagrammer(ordliste):
    anagram_par = []
    for i in range(len(ordliste)):
        for j in range(i + 1, len(ordliste)):
            if sorted(ordliste[i]) == sorted(ordliste[j]):
                anagram_par.append((ordliste[i], ordliste[j]))
    return anagram_par

# Test
ord = ['abc', 'bca', 'xyz', 'cab', 'zyx']
print(finn_anagrammer(ord))
# [('abc', 'bca'), ('abc', 'cab'), ('bca', 'cab'), ('xyz', 'zyx')]

Koden verkar, men er treg for store ordlister.