Big-O beskriver hur en algoritms körtid eller minneskonsumtion växer när indatastorleken n växer. Den fångar det värsta fall asimptotiska beteendet och ignorerar konstanter och termer av låg ordning.
Vi bryr oss om tillväxthastighet, inte exakta stegräkningar. O(2n + 5) är helt enkelt O(n) eftersom konstanter och mindre termer blir irrelevanta när n växer.
| Big-O | Namn | Exempel |
|---|
| O(1) | konstant | arrayindexuppslagning |
| O(log n) | logaritmisk | binär sökning |
| O(n) | linjär | genomsökning av lista |
| O(n log n) | linjär-logaritmisk | merge sort |
| O(n²) | kvadratisk | kapslade loopar |
| O(2ⁿ) | exponentiell | naiv undermängd |
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 döljer konstanter: en O(n)-algoritm med en stor konstant kan förlora mot O(n log n) på små indata. Spåra också rymdkomplexitet, inte bara tid.
Big-O låter dig jämföra algoritmer utan att köra dem eller oroa dig för hårdvara.
Det förutspår vilka lösningar som överlever när indata växer från hundratals till miljoner — skillnaden mellan en funktion som skalas och en som tar timeout.
Det är det ordförråd som varje ingenjör använder för att resonera om prestanda.