Big-O notation (O(1)/O(log n)/O(n)/O(n log n)/O(n²))

Kommunikation og IT A · HTX · A-niveau · Datastrukturer og algoritmer

💻 Big-O notation

Big-O beskriver algoritmers tids- og pladskompleksitet i worst case som funktion af inputstørrelse n.

| Notation | Navn | Eksempel |

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

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

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

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

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

| O(n²) | Kvadratisk | Bubble sort, nested loops |

| O(2ⁿ) | Eksponentiel | Naive Fibonacci |

Eksempel på analyse:

```python

def find(liste, mål): # O(n) — gennemgår hele listen

for x in liste:

if x == mål:

return True

return False

def opslag(dict, nøgle): # O(1) — hash-tabel

return dict.get(nøgle)

```

Tommelfingerregel: nested loop → O(n²). Halvering per trin → O(log n).

Praktisk: O(n log n) er acceptabelt for n=10⁶. O(n²) er for langsomt ved n>10⁴.

Læringsmål

• Bestemme Big-O kompleksiteten for simple algoritmer
• Rangordne kompleksitetsklasser fra hurtigst til langsomst
• Identificere O(n²) mønstre (nested loops) og forbedre dem
• Analysere tid og hukommelse for egne programmer

Sådan kan du arbejde med emnet

• Bestem tidskompleksiteten for en algoritme der gennemløber en liste to gange indlejret
• Sammenlign O(n) og O(n²) ved at beregne antal operationer for n=10, 100 og 1000
• Forklar hvorfor en algoritme med O(log n) er hurtigere end O(n) for store datamængder

Træningsforslag

• Mål køretid for bobblesort vs. quicksort på 10.000 elementer
• Find O(n²) mønstre i din kode og omskriv til O(n)
• Løs BigO.io interaktive øvelser