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

It A · STX · A-niveau · Datastrukturer og algoritmer

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

Big-O notation udtrykker algoritmeirs tidskompleksitet (og rumkompleksitet) som funktion af inputstørrelse n i worst case.

Kompleksitetsklasser (hurtigst til langsomst): O(1) = konstant tid (hash-tabelopslag, indeksadgang i array). O(log n) = logaritmisk (binær søgning, BST-operationer, heap). O(n) = lineær (linær søgning, én for-løkke). O(n log n) = linearitmisk (merge sort, quick sort i gennemsnit, heap sort). O(n²) = kvadratisk (bubble sort, selection sort, dobbelt indlejret løkke). O(2ⁿ) = eksponentiel (naiv rekursiv Fibonacci, problemet med handelsrejsendes). O(n!) = faktoriel (brute-force rejsende sælger, permutationer).

Rumkompleksitet: O(1) = in-place sortering (insertion sort). O(n) = merge sort (hjælpe-array).

Amortiseret analyse: list.append i Python er O(1) amortiseret — lejlighedsvis O(n) ved resize.

Praktisk: O(n log n) er "godt nok" for de fleste opgaver. O(n²) problematisk ved n > 10.000. Big-O ignorerer konstanter: O(100n) = O(n).

Læringsmål

• Redegøre for big-O notation som mål for tidskompleksitet
• Bestemme tidskompleksiteten for en given algoritme
• Sammenligne algoritmers effektivitet ved hjælp af big-O

Sådan kan du arbejde med emnet

• Angiv tidskompleksiteten for opslag i et array, binær søgning, bobblesort og merge sort
• Beregn, hvad der er det approksimative antal operationer for n=1000 for O(n) og O(n^2)
• Diskutér, hvad der er praktisk forskel på O(n log n) og O(n^2) ved store datasæt

Arbejd iterativt med prototyper og dokumentation. Test, evaluér og dokumentér.