Ga naar hoofdinhoud

7.5 O(log n) — logaritmische tijd

Leerdoel: je herkent algoritmes die bij elke verdubbeling van n maar één stap extra doen, en je ziet visueel een bijna platte curve.

Hoe gedraagt het zich?​

O(log n) betekent: bij elke verdubbeling van n komt er één stap bij. Dat is bizar weinig groei.

nlog₂ n
10~3
100~7
1.000~10
1.000.00020
1.000.000.00030

Een miljard elementen → 30 stappen. Dat is O(log n) in actie.

Analogie: een woord opzoeken in het woordenboek. Sla open in het midden, beslis "linker- of rechterhelft", herhaal. Bij elke verdubbeling van het woordenboek heb je maar één extra slag nodig.

Hoe ontstaat het?​

O(log n) ontstaat bijna altijd door halveren: bij elke stap snij je het werk doormidden. Dat is precies wat binair zoeken doet.

Vergelijk:

  • Bij O(n) doe je n stappen door alles te bekijken.
  • Bij O(log n) doe je log₂(n) stappen door steeds de helft weg te gooien.

Voorspel​

Op een lijst van 1.000.000 elementen: hoeveel vergelijkingen doet binair zoeken in het slechtste geval?

Antwoord

Ongeveer 20 vergelijkingen. log₂(1.000.000) ≈ 19.9.

Vergelijk met lineair zoeken op dezelfde lijst: 1.000.000 vergelijkingen. Het verschil is een factor 50.000.

Run — kijk hoe het groeit​

Python
Code-omgeving wordt voorbereid…
Wat zie je?

Op een log-schaal voor n zie je een rechte lijn die maar langzaam stijgt. Elke verdubbeling van n voegt slechts één stap toe.

  • 10 → 4 stappen
  • 100 → 7 stappen
  • 1.000 → 10 stappen
  • 1.000.000 → 20 stappen

Op een normale (lineaire) x-as zou dezelfde lijn er bijna vlak uitzien — de groei is zó traag dat je hem nauwelijks ziet.

Welke algoritmes zijn O(log n)?​

In dit curriculum:

Belangrijk: binair zoeken werkt alleen op een gesorteerde lijst. Geen sortering, geen O(log n). Sorteren is zelf duurder (O(n log n) of slechter), dus binair zoeken loont alleen als je vaak in dezelfde gesorteerde lijst zoekt.

Door naar stap 6: O(n²) — kwadratisch →.