Big-O beskriver hvordan kjøretiden eller minneforbruket til en algoritme vokser når inndatastørrelsen n vokser. Det fanger worst-case asymptotisk oppførsel, og ignorerer konstanter og lavereordens ledd.
Vi bryr oss om veksthastighet, ikke nøyaktige trinnantall. O(2n + 5) er ganske enkelt O(n) fordi når n blir stor, slutter konstanter og mindre ledd å være viktige.
| Big-O | Navn | Eksempel |
|---|
| O(1) | konstant | array index lookup |
| O(log n) | logaritmisk | binary search |
| O(n) | lineær | scanning av en liste |
| O(n log n) | linearitmisk | merge sort |
| O(n²) | kvadratisk | nestede løkker |
| O(2ⁿ) | eksponentiell | naive subsets |
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 stor konstant kan tape mot O(n log n) på små inndataer. Spor også space kompleksitet, ikke bare tid.
Big-O lar deg sammenligne algoritmer uten å kjøre dem eller å bekymre deg for maskinvare.
Det forutsier hvilke løsninger som overlever når inndataer vokser fra hundrevis til millioner — forskjellen mellom en feature som skaleres og en som timeout.
Det er vokabularet som hver ingeniør bruker for å resonnere om ytelse.