Tidskompleksitet (Big-O)

Programmering B · HTX · B-niveau · Datastrukturer og algoritmer

💻 Big-O notation

Big-O beskriver algoritmers tidskompleksitet — hvordan køretid vokser med input-størrelse n.

Klasser fra hurtigst til langsomst:

```

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)

```

Eksempler:

| Notation | Navn | Eksempel |

|----------|------|----------|

| O(1) | Konstant | Dictionary-lookup |

| O(log n) | Logaritmisk | Binær søgning |

| O(n) | Lineær | Lineær søgning |

| O(n log n) | Linearitmisk | Quicksort, Merge sort |

| O(n²) | Kvadratisk | Boble-sortering |

| O(2^n) | Eksponentiel | Naiv Fibonacci |

Analyse — tæl dominerende operation:

```python

def find_par(liste): # O(n²)

for i in range(len(liste)): # n iterationer

for j in range(i+1, len(liste)): # n iterationer

if liste[i] + liste[j] == 10:

print(liste[i], liste[j])

```

Rumkompleksitet (Space complexity): hukommelse brugt af algoritme.

Praktisk tommelfingerregel:

• n = 10^8: kun O(1), O(log n), O(n) er realistiske
• n = 10^6: O(n log n) virker
• n = 10^4: O(n²) virker
• n = 20: O(2^n) virker måske

Amortiseret analyse: list.append() er O(1) amortiseret selvom den lejlighedsvis resizer (O(n)).

Læringsmål

• Bestemme Big-O kompleksitet for simple algoritmer
• Forklare forskellen på O(n) og O(n²) med et konkret eksempel
• Optimere en O(n²) algoritme til O(n) ved brug af dictionary
• Forstå rumkompleksitet

Sådan kan du arbejde med emnet

• Forklar hvad O(n) og O(n^2) betyder med konkrete eksempler på algoritmer
• Vurdér tidskompleksiteten af en simpel funktion, der gennemløber en liste én gang
• Diskutér hvorfor tidskompleksitet bliver vigtigere, når datamængden bliver meget stor

Træningsforslag

• Analyser Big-O for dine egne algoritmer
• Optimer en Two Sum O(n²) løsning til O(n) med dictionary
• Mål faktisk køretid med time.time() og sammenlign med Big-O forudsigelse