3.1 Algoritmisk tenkning og effektivitet

Algoritmisk tenkning og effektivitet

Når du programmerer, finnes det ofte mange måter å løse samme problem på. Men ikke alle løsninger er like gode. Noen programmer kjører raskt selv med store datamengder, mens andre henger seg opp når dataene vokser.

I dette kapittelet skal du lære å:
- Tenke algoritmisk og strukturere løsninger
- Analysere hvor effektiv en algoritme er
- Forstå Big O-notasjon
- Optimalisere koden din for bedre ytelse

Dette er grunnleggende ferdigheter for enhver som jobber med programmering og store datasett.

En god algoritme har disse egenskapene:
- Definert input: Vi vet hva som går inn
- Definert output: Vi vet hva som skal ut
- Utvetydig: Hvert steg er klart definert
- Endelig: Algoritmen stopper etter et visst antall steg
- Effektiv: Den løser problemet på en fornuftig måte

Eksempel på en enkel algoritme for å finne det største tallet i en liste:
1. Start med første tall som "størst så langt"
2. Gå gjennom resten av listen
3. Hvis du finner et større tall, oppdater "størst så langt"
4. Når listen er ferdig, returner "størst så langt"

La oss se på to måter å sjekke om en liste har duplikater:

Løsning 1: Sammenligne hvert 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øsning 2: Bruke et 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øsningene gir riktig svar, men løsning 2 er mye raskere når listen er stor. Hvorfor? Det handler om hvor mange operasjoner som må utføres.

Big O-notasjon: En matematisk måte å beskrive hvordan kjøretiden vokser når input blir større. Vi fokuserer på den dominerende faktoren og ignorerer konstanter.

Vanlige tidskompleksiteter (fra best til verst):

La oss analysere tidskompleksiteten til våre duplikat-funksjoner:

Løsning 1: Nestede 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 iterasjoner
- Indre løkke: opptil n iterasjoner
- Totalt: omtrent n × n = n² sammenligninger
- Tidskompleksitet: O(n²)

Løsning 2: Bruke set

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

- set(liste): går gjennom listen én gang (n operasjoner)
- len(): konstant tid for begge kall
- Tidskompleksitet: O(n)

Forskjellen i praksis:
- Med 100 elementer: O(n²) = 10,000 operasjoner vs O(n) = 100 operasjoner
- Med 1,000 elementer: O(n²) = 1,000,000 operasjoner vs O(n) = 1,000 operasjoner
- Med 10,000 elementer: O(n²) = 100,000,000 operasjoner vs O(n) = 10,000 operasjoner

Dette er grunnen til at tidskompleksitet betyr noe!

Hva er tidskompleksiteten til denne funksjonen?

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

To funksjoner finner om et tall finnes i en 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 bruker vi Big O-notasjon for plasskompleksitet.

Eksempler:

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 velge mellom tid og plass. Noen ganger kan vi bruke mer minne for å få raskere kjøretid (caching/memoisering).

La oss se på tre implementasjoner av Fibonacci-tallene og deres effektivitet:

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

Sammenligning:
- V1: Eksponentiell tid, kan ikke håndtere store tall
- V2: Lineær tid, bruker ekstra minne for cache
- V3: Lineær tid, minimal minnebruk - beste løsningen!

Se 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 å virke først: Skriv kode som løser problemet korrekt
2. Mål ytelsen: Bruk profileringsverktøy for å finne flaskehalser
3. Optimaliser der det trengs: Fokuser på de delene som faktisk er trege
4. Test at det fortsatt virker: Verifiser at optimaliseringen ikke introduserer bugs

Når bør du tenke på effektivitet?
- Når du jobber med store datasett (tusenvis eller millioner av elementer)
- I funksjoner som kalles veldig mange ganger
- Når brukerne opplever treg respons

Når er det mindre viktig?
- For små datasett (under 100 elementer)
- Kode som bare kjøres én gang
- Når lesbarhet er viktigere enn hastighet

Huskeregel: Skriv lesbar kode først. Optimaliser senere hvis nødvendig.

Python har en innebygd modul for å måle hvor lang tid kode tar:

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 hvordan forskjellen mellom O(n²) og O(n) påvirker kjøretiden!

Du har denne funksjonen som teller hvor mange ganger hvert ord forekommer:

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

Hva er et bedre alternativ?

Se på denne funksjonen som sjekker om en 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 tenkning:
- En algoritme er en steg-for-steg løsning på et problem
- Samme problem kan løses på mange måter 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å hvis mulig
- O(2ⁿ): Eksponentiell tid - kun for små input

Tidskompleksitet:
- Beskriver hvor mange operasjoner som kreves
- Fokuserer på worst-case scenario
- Ignorerer konstante faktorer

Plasskompleksitet:
- Beskriver hvor mye minne som brukes
- Ofte trade-off mellom tid og plass

Optimalisering:
- Få koden til å virke først
- Mål ytelsen før du optimaliserer
- Fokuser på flaskehalser
- Ikke optimaliser for tidlig

Praktiske tips:
- Unngå nestede løkker over samme data når mulig
- Bruk innebygde datastrukturer (dict, set) for raske oppslag
- Bruk list comprehensions og generator expressions
- Test med realistiske datastørrelser

Samleoppgaver

Her er noen oppgaver som kombinerer flere konsepter fra 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 en funksjon som finner de 3 største tallene i en stor liste med millioner av tall.

Hvilken tilnærming gir best ytelse?

A) Sorter hele listen og ta de tre siste
B) Gå gjennom listen én gang og hold styr på de tre største
C) Bruk Pythons heapq.nlargest()
D) Bruk max() tre ganger og fjern elementet hver gang

Du har skrevet denne koden for å finne alle anagram-par i en 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 virker, men er treg for store ordlister.