Groeikoers, Niet Absoluut Kosten
Big O: Het Meten Van Hoe Snel Kosten Groeien
Big O notatie meet de groeiwijze van de kosten van een algoritme - niet de absoluut kosten.
De vraag die Big O beantwoordt: verdubbelt de werklast als de invoergroote N verdubbelt? Verviervoudigt? Blijft vlak?
Het 'O' staat voor 'orde van grootte'. Het uitdrukking binnen de haakjes beschrijft de vorm van de groeivooruitzichten.
Kleine complexiteitsklassen:
- O(1) — constant: kosten groeien niet. Voorbeeld: zoeken naar een waarde door de index in een array. Of het array heeft 10 items of 10 miljoen, één lookup blijft één lookup.
- O(N) — lineair: kosten groeien met de invoer. Voorbeeld: lezen van elk item in een lijst. Dubbel de lijst, verdubbel de leesacties.
- O(N²) — kwadraat: kosten groeien als het vierkant van de invoer. Voorbeeld: vergelijken van elk item met elk ander item. Dubbel N, vervierd de werklast.
Groeikomparistabel:
| N | O(1) | O(N) | O(N²) |
|---|------|------|-------|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
Bij N=10 lijkt de verschil klein. Bij N=1.000 wordt de kloof enorm.
Vergelijk O(N) met O(N²)
Gebruik de groeikomparistabel hierboven.
Bij N=1.000: O(N) vereist 1.000 operaties. O(N²) vereist 1.000.000 operaties.
Hoe Codestructuur Complexiteit Onthult
Hoe Big O uit Code te Identificeren
Big O schuilt in de vorm van je code. Vier patronen dekken de meeste gevallen:
Enkele lus door N items: O(N)
# O(N): één doorloop van de lijst
for item in list_of_n_items:
process(item)Dubbel lus, elke lus over N items: O(N²)
# O(N²): elk item wordt gekoppeld aan elk ander item
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)Constante lookup: O(1)
Toegang tot arrayindex, zoekopdracht in hash tabel — één stap ongeacht de grootte.
Verdeel-en-overwinnen (probleem halveren in elke stap): O(log N)
Binair zoeken: elke controle verkleint het resterende aantal items.
---
Verhulde O(N²): een lijst binnen een lus
# Dit ziet er uit als O(N) maar het is eigenlijk O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # scan van alle elementen in visited: O(N)
visited.append(item) # de hele lus: O(N²)De if item not in visited regel scannet elk element van visited bij elke iteratie. Een scans van een lijst kost O(N). Een lus die N keer wordt uitgevoerd, elke keer O(N) werk: O(N) × O(N) = O(N²).
Dit patroon komt voor in 1.000+ open-source projecten. De oplossing kost één karakter: vervang visited = [] door visited = set(). Testen van lidmaatschap van een set kost O(1), niet O(N). Eén wijziging. Dezelfde resultaten. 1.000× sneller bij N=1.000.
Classificeer & Herstel Deze Code
Lees deze code:
result = []
for name in student_names:
if name not in result:
result.append(name)Theorie Ontmoet Praktijk
Big O in de Wilde
Big O is niet alleen theorie. Het onderscheidt programma's die in seconden worden afgerond van programma's die 17 minuten nodig hebben — op precies dezelfde taak.
Echte voorbeeld: detectie van afhankelijkheidscycli in een build systeem.
Als je software installeert, verwerft je computer een grafiek van afhankelijkheden: pakket A heeft B nodig, B heeft C nodig, enzovoorts. Een build systeem controleert deze grafiek op cycli.
Een O(N²) algoritme voor cycli-detectie werkt prima bij N=100 pakketten. Bij N=50,000 pakketten (een echt project): het kost 17 minuten. De O(N) oplossing: 10 seconden.
Deze exacte fout bestaat in GHC (Haskell compiler), pip (Python package manager), Maven (Java build systeem), Cargo (Rust package manager) & 1.000+ andere projecten.
Niet omdat hun auteurs onverschillig waren. visited = [] werd geschreven toen N klein was. De code versteende. N groeide. Niemand merkte het op tot de build een half uur duurde.
Big O is de taal die je laat wat er gebeurde — & het fixen.
---
Wil je dieper gaan? Ons unhamming cursus bevat een volledig hoofdstuk over Big O, MOAD-0001 (een echt O(N²) defect gevonden in 1.000+ open-source projecten), & waarom het benoemen van een patroon je laat het overal vinden. Zie [De Missende Hoofdstuk: Algoritmische Complexiteit](/en/un/unhamming_algorithmic_complexity).
Voorspel de Bouwtijden
Een build systeem gebruikt O(N²) cycli-detectie.
Gemeten bouwtijden:
- N=100 pakketten: 0.01 seconden
- N=1,000 pakketten: 1 seconde
Voor O(N²): de tijd schaalt zich als (N_new / N_old)².
Voor O(N): de tijd schaalt zich als (N_new / N_old).