Tillväxthastigheter, inte absoluta kostnader
Big O: Mäta hur snabbt kostnader växer
Big O-notation mäter tillväxthastigheten för en algoritms kostnad — inte den absoluta kostnaden.
Frågan som Big O besvarar: när inmatningsstorleken N fördubblas, fördubblas arbetet? Fyrdubblas det? Förblir det oförändrat?
'O' står för 'storleksordning'. Uttrycket innanför parenteserna beskriver formen på tillväxtkurvan.
Viktiga komplexitetsklasser:
- O(1) — konstant: kostnad växer inte. Exempel: slå upp ett värde efter index i en array. Oavsett om arrayen har 10 objekt eller 10 miljoner, förblir en sökning en sökning.
- O(N) — linjär: kostnad växer med inmatningen. Exempel: läsa varje objekt i en lista en gång. Dubbel lista, dubbla läsningar.
- O(N²) — kvadratisk: kostnad växer som kvadraten på inmatningen. Exempel: jämför varje objekt med varje annat objekt. Dubbel N, fyrdubbel arbete.
Tabell för tillväxtjämförelse:
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
Vid N=10 ser skillnaden liten ut. Vid N=1000 blir klyftan enorm.
Jämför O(N) med O(N²)
Använd tillväxtjämförelsetabellen ovan.
Vid N=1000: O(N) kräver 1000 operationer. O(N²) kräver 1000000 operationer.
Hur kodstruktur avslöjar komplexitet
Hur man identifierar Big O från kod
Big O döljer sig i formen på din kod. Fyra mönster täcker de flesta fallen:
Enkel slinga över N objekt: O(N)
# O(N): ett pass genom listan
for item in list_of_n_items:
process(item)Nästlade slingor, var över N objekt: O(N²)
# O(N²): varje objekt ihopparslat med varje annat objekt
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Konstant-tid sökning: O(1)
Arrayindex-åtkomst, hash-tabell sökning — ett steg oavsett storlek.
Dela-och-härska (skär problemet i hälften varje steg): O(log N)
Binär sökning: varje kontroll halverar de återstående objekten.
---
Dold O(N²): en lista inuti en slinga
# Det här ser ut som O(N) men det är faktiskt O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # skannar all av visited: O(N)
visited.append(item) # hela slingen: O(N²)Raden if item not in visited skannar varje element i visited varje iteration. Ett listascan kostar O(N). En slinga som körs N gånger, var gång gör O(N) arbete: O(N) × O(N) = O(N²).
Det här mönstret förekommer i 1000+ projekt med öppen källkod. Fixet tar ett tecken: ersätt visited = [] med visited = set(). Set-medlemskapstestning kostar O(1), inte O(N). En förändring. Samma resultat. 1000× snabbare vid N=1000.
Klassificera & fixa denna kod
Läs denna kod:
result = []
for name in student_names:
if name not in result:
result.append(name)Teori möter praktik
Big O i verkligheten
Big O är inte bara teori. Det skiljer program som slutförs på sekunder från program som tar 17 minuter — på exakt samma uppgift.
Verkligt exempel: beroendecykeldetektion i ett byggsystem.
När du installerar programvara löser din dator en graf av beroenden: paket A behöver B, B behöver C, och så vidare. Ett byggsystem kontrollerar denna graf för cykler.
En O(N²) cykeldetektor fungerar bra vid N=100 paket. Vid N=50000 paket (ett verkligt projekt): det tar 17 minuter. O(N)-fixet: 10 sekunder.
Denna exakta defekt existerar i GHC (Haskell compiler), pip (Python pakethanterare), Maven (Java byggsystem), Cargo (Rust pakethanterare) & 1000+ andra projekt.
Inte för att deras författare var slarviga. visited = [] skrevs när N var liten. Koden hårdnades. N växte. Ingen märkte förrän bygget tog en halv timme.
Big O är det ordförråd som låter dig namnge vad som hände — & fixa det.
---
Vill du gå djupare? Vår unhamming-kurs innehåller ett fullständigt kapitel om Big O, MOAD-0001 (en verklig O(N²)-defekt funnen i 1000+ projekt med öppen källkod) & varför namngivning av ett mönster låter dig hitta det överallt. Se The Missing Chapter: Algorithmic Complexity.
Förutsäga byggtiderna
Ett byggsystem använder O(N²) cykeldetektion.
Uppmätta byggtider:
- N=100 paket: 0.01 sekunder
- N=1000 paket: 1 sekund
För O(N²): tiden skalar som (N_new / N_old)².
För O(N): tiden skalar som (N_new / N_old).