3.1 Algoritmisk tenkning og effektivitet

Samme svar, helt ulik fart

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 enorme datamengder, mens andre henger seg fullstendig opp når dataene vokser. Forskjellen ligger i algoritmen – steg-for-steg-oppskriften for å løse et problem.

En god algoritme har noen kjennetegn. Den har definert input, så vi vet hva som går inn. Den har definert output, så vi vet hva som skal ut. Den er utvetydig, så hvert steg er klart. Den er endelig, så den stopper. Og den er effektiv, så den løser problemet på en fornuftig måte.

La oss se forskjellen i praksis. Du skal sjekke om en liste inneholder duplikater. Én løsning sammenligner hvert element med alle andre, i to nøstede løkker. En annen gjør hele jobben på én linje ved å lage en mengde og sammenligne lengder: len(liste) != len(set(liste)). Begge gir riktig svar. Men når listen blir stor, er den andre enormt mye raskere. Hvorfor? Det handler om hvor mange operasjoner som faktisk må utføres – og det er det vi nå skal lære å måle.

Big O og tidskompleksitet

For å sammenligne algoritmer trenger vi et språk. Tidskompleksitet er et mål på hvor mange operasjoner en algoritme må utføre, sett som en funksjon av input-størrelsen, som vi kaller n. Vi beskriver den med Big O-notasjon, som fokuserer på hvordan kjøretiden vokser når n blir stor – vi ser på den dominerende faktoren og ignorerer konstanter.

Noen kompleksiteter går igjen, fra best til verst. O(1) er konstant tid, like raskt uansett størrelse, som å hente et listeelement med indeks. O(log n) er logaritmisk, der søkeområdet halveres hver gang, som i binærsøk. O(n) er lineær, proporsjonal med størrelsen, som å gå gjennom en liste én gang. O(n log n) kjennetegner effektive sorteringsalgoritmer. O(n²) er kvadratisk, typisk for nøstede løkker over samme data. Og helt i den dyre enden ligger O(2ⁿ), eksponentiell, og O(n!), faktoriell.

Nå skjønner vi duplikat-eksempelet. Den nøstede løkken er O(n²): en ytre løkke på n og en indre på opptil n gir omtrent n × n sammenligninger. Set-løsningen er O(n): den går gjennom listen bare én gang. Forskjellen er svimlende. Med 10 000 elementer betyr O(n²) hundre millioner operasjoner, mens O(n) bare betyr ti tusen. Big O beskriver dessuten alltid worst case – verste tenkelige tilfelle – så vi får en garanti for at algoritmen aldri blir tregere enn det.

Plass, tid og Fibonacci

Tid er ikke det eneste vi bryr oss om. Plasskompleksitet måler hvor mye minne en algoritme bruker, også uttrykt med Big O. En sumfunksjon som bare holder én totalvariabel bruker O(1) plass – konstant, uansett listestørrelse. En funksjon som lager en ny liste like stor som input, bruker O(n) plass. Ofte må vi velge mellom tid og plass: vi kan bruke mer minne for å oppnå raskere kjøretid, og motsatt.

Fibonacci-tallene viser dette vakkert. En naiv rekursiv versjon, fib(n-1) + fib(n-2), er katastrofalt treg – O(2ⁿ) – fordi den regner ut de samme tallene om og om igjen. Med memoisering, der vi lagrer allerede beregnede svar i en cache, faller tiden til O(n), men vi bruker O(n) ekstra minne på cachen. Den iterative versjonen, som bare holder de to siste tallene og løkker oppover, er like rask – O(n) tid – men bruker bare O(1) plass:

def fibonacci(n):
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Dette er den beste løsningen: rask og minnegjerrig. Memoisering er et eksempel på en trade-off der vi ofrer minne for fart, mens den iterative versjonen unngår å betale den prisen i det hele tatt.

Når – og når ikke – å optimalisere

Det er fristende å jage fart hele tiden, men her er en advarsel. Donald Knuth sa berømt at «premature optimization is the root of all evil». Prematur optimalisering er å bruke for mye tid på å finpusse ytelsen før det er nødvendig. Den fornuftige rekkefølgen er: få det til å virke først, mål ytelsen for å finne de virkelige flaskehalsene, optimaliser bare der det trengs, og test at koden fortsatt virker etterpå.

Python har innebygd måling i modulen timeit. Kjører du duplikat-funksjonene på 10 000 elementer, kan O(n²)-versjonen ta flere sekunder mens O(n)-versjonen er ferdig på et blunk – tusenvis av ganger raskere. Slik kan du dokumentere forbedringen i stedet for å gjette.

Når bør du tenke på effektivitet? Når du jobber med store datasett, i funksjoner som kalles svært mange ganger, eller når brukerne opplever treg respons. Når betyr det mindre? For små datasett under hundre elementer, for kode som bare kjøres én gang, og når lesbarhet er viktigere enn hastighet. To praktiske grep løser de fleste problemer: unngå nøstede løkker over samme data, og bruk ordbøker og mengder for raske oppslag. Husk også at samme algoritme kan ha ulik best case og worst case – en funksjon som sjekker om en liste er sortert, returnerer kjapt hvis de to første elementene er feil (O(1)), men må gå gjennom hele listen hvis den faktisk er sortert (O(n)).

Oppsummering

Vi så at to programmer kan gi samme svar, men være tusenvis av ganger fra hverandre i fart. En algoritme er en presis, endelig oppskrift, og Big O-notasjon lar oss beskrive hvordan kjøretiden vokser med input-størrelsen n: fra det raske O(1), O(log n) og O(n), via O(n log n), til det dyre O(n²) og eksponentielle O(2ⁿ). Tidskompleksitet måler operasjoner og fokuserer på worst case, mens plasskompleksitet måler minnebruk.

Fibonacci viste tid/plass-avveiningen: naiv rekursjon er O(2ⁿ), memoisering bytter minne mot fart, og den iterative versjonen er både rask og minnegjerrig. Til slutt lærte vi disiplinen: ikke optimaliser prematurt. Få koden til å virke, mål med timeit, og forbedre bare der det faktisk trengs – gjerne ved å unngå nøstede løkker og bruke ordbøker og mengder. I neste kapittel går vi dypere inn i søke- og sorteringsalgoritmer.