Big-O beskriver, hvordan en algoritmes køretid eller hukommelse vokser, når inputstørrelsen n vokser. Den fanger den værste tilfælde asymptotiske adfærd, mens konstanter og lavere-ordensled ignoreres.
Vi bekymrer os om vækstraten, ikke præcise skridtantal. O(2n + 5) er blot O(n), fordi når n vokser stort, stopper konstanter og mindre led med at betyde noget.
| Big-O | Navn | Eksempel |
|---|
| O(1) | konstant | array-indeksopslag |
| O(log n) | logaritmisk | binær søgning |
| O(n) | lineær | scanning af en liste |
| O(n log n) | linearitmisk | flettesortering |
| O(n²) | kvadratisk | indlejrede løkker |
| O(2ⁿ) | eksponentiel | naive delmængder |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O skjuler konstanter: en O(n)-algoritme med en enorm konstant kan tabe for O(n log n) på små input. Spor også rum kompleksitet, ikke kun tid.
Big-O lader dig sammenligne algoritmer uden at køre dem eller bekymre dig om hardware.
Det forudsiger, hvilke løsninger der overlever, når input vokser fra hundreder til millioner — forskellen mellem en funktion, der skaleres, og en der times ud.
Det er det ordforråd, som enhver ingeniør bruger til at ræsonnere om præstationen.