Hoe Codestructuur de Complexiteit Onthult

Hoe je Big O Herkent in Code

Big O verschuilt zich in de vorm van je code. Vier patronen dekken de meeste gevallen:

Enkele lus over N items: O(N)

# O(N): één keer door de lijst
for item in list_of_n_items:
    process(item)

Geneste lussen, elk over N items: O(N²)

# O(N²): elk item 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)

Opzoeken met constante tijd: O(1)

Array-indexbenadering, hash-tabel opzoeken — één stap ongeacht de grootte.

Verdeel-en-heers (halveert het probleem bij elke stap): O(log N)

Binair zoeken: elke controle halveert de resterende items.

---

Verborgen O(N²): een lijst in een lus

# Dit ziet eruit als O(N) maar het is eigenlijk O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scant alle visited: O(N)
        visited.append(item)  # de hele lus: O(N²)

De regel if item not in visited scant elk element van visited bij elke iteratie. Een listscan kost O(N). Een lus die N keer draait, elk keer O(N) werk doet: O(N) × O(N) = O(N²).

Dit patroon komt voor in 1.000+ open-source projecten. De fix kost één teken: vervang visited = [] door visited = set(). Set-lidmaatschapstesting kost O(1), niet O(N). Één verandering. Hetzelfde resultaat. 1.000× sneller bij N=1.000.

Classificeer & Repareer 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 Praktijk

Big O is niet alleen theorie. Het scheidt programma's die in seconden klaar zijn van programma's die 17 minuten nodig hebben — voor dezelfde taak.

Real voorbeeld: detectie van afhankelijkheidscycli in een bouwsysteem.

Wanneer je software installeert, lost je computer een grafiek van afhankelijkheden op: pakket A heeft B nodig, B heeft C nodig, enzovoort. Een bouwsysteem controleert deze grafiek op cycli.

Een O(N²) cylusdetectiealgoritme werkt prima bij N=100 pakketten. Bij N=50.000 pakketten (een echt project): het duurt 17 minuten. De O(N) fix: 10 seconden.

Dit exacte defect bestaat in GHC (Haskell-compiler), pip (Python-pakketbeheerder), Maven (Java-bouwsysteem), Cargo (Rust-pakketbeheerder) & 1.000+ andere projecten.

Niet omdat hun auteurs onvoorzichtig waren. visited = [] werd geschreven toen N klein was. De code verstarde. N groeide. Niemand merkte het totdat de build een half uur duurde.

Big O is het vocabulaire waarmee je kunt benoemen wat er gebeurde — & het repareren.

---

Wil je dieper gaan? Onze 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 het je overal laat vinden. Zie The Missing Chapter: Algorithmic Complexity.

Voorspel de Bouwcijfers

Een bouwsysteem gebruikt O(N²) cylusdetectie.

Gemeten bouwcijfers:

- N=100 pakketten: 0,01 seconden

- N=1.000 pakketten: 1 seconde

Voor O(N²): tijd schaalt als (N_nieuw / N_oud)².

Voor O(N): tijd schaalt als (N_nieuw / N_oud).