Hoe snel? Grote-O-notatie

Bij een miljard stappen per seconde kost een n²-methode op een miljoen waarden ongeveer 17 minuten; een n log n-methode kost 0.02 seconden.

Groei telt meer dan het exacte aantal

Tot nu toe telden we stappen exact: 45 vergelijkingen, 4 verwisselingen, 20 controles. Exacte aantallen zijn nuttig voor kleine voorbeelden, maar hangen af van details zoals vroeg stoppen bij bubblesort of de keuze van een spil. Als de invoer groot wordt, overheerst één ding: hoe het aantal groeit als n groeit. Een algoritme waarvan de stappen groeien als n² verliest uiteindelijk van een dat groeit als n log n, hoe zorgvuldig het eerste ook is geoptimaliseerd.

Grote-O-notatie is de verkorte schrijfwijze voor die groei. Schrijven dat een algoritme O(n²) is, uitgesproken ‘grote O van n kwadraat’, betekent dat het aantal stappen voor grote n hoogstens een constante maal n² is. Twee regels maken het gebruik eenvoudig. Laat constante factoren weg: 3n en n/2 zijn beide O(n). Behoud alleen de snelst groeiende term: n²/2 − n/2, de vergelijkingen van selectionsort, is O(n²), omdat voor grote n het n²-deel bijna alles vormt. De cursus 6.006 van MIT gebruikt hetzelfde idee om gegevensstructuren en sorteermethoden op hun asymptotische looptijd te vergelijken.

Veelvoorkomende groeisnelheden

• O(1), constant. Het werk hangt niet af van n: de eerste waarde van een lijst lezen of een waarde op een bekende positie.
• O(log n), logaritmisch. Elke stap halveert het probleem: binair zoeken. Een miljoen waarden, ongeveer 20 stappen.
• O(n), lineair. Elke waarde wordt eenmaal verwerkt: lineair zoeken, de grootste waarde vinden, een lijst optellen.
• O(n log n). Mergesort en gemiddeld quicksort. Het beste dat sorteren met vergelijkingen kan bereiken.
• O(n²), kwadratisch. Elk paar wordt bekeken: bubblesort, selectionsort en insertionsort in het slechtste geval, of twee geneste lussen.
• O(2ⁿ), exponentieel. Het werk verdubbelt met elk extra item: elke deelverzameling van n items proberen of n schijven in de Torens van Hanoi verplaatsen.

Wat de getallen in seconden betekenen

Stel dat een computer een miljard (10⁹) basisstappen per seconde uitvoert, een redelijk rond getal voor één processorkern. Dit betekent elke groeisnelheid voor een miljoen waarden. O(log n) is ongeveer 20 stappen, ver onder een microseconde. O(n) is een miljoen stappen, één milliseconde. O(n log n) is ongeveer 20 miljoen stappen, 0.02 seconden. O(n²) is 10¹² stappen, duizend seconden, ongeveer 17 minuten. O(2ⁿ) kan niet worden voltooid: 2 tot de macht een miljoen heeft meer dan 300 000 cijfers. Daarom is het juiste algoritme kiezen meestal veel belangrijker dan een snellere computer kopen. Een tienmaal snellere machine maakt van 17 minuten 1.7 minuten; overstappen van O(n²) naar O(n log n) maakt er een vijftigste seconde van.

Grote O uit code aflezen

Vaak kun je de groeisnelheid direct uit de vorm van de code aflezen. Eén lus over de lijst is O(n). Twee lussen, één binnen de andere, beide over de lijst, zijn O(n²): voor elk van de n buitenrondes doet de binnenlus maximaal n rondes. Een lus die elke keer een getal halveert, zoals while (n > 1) n = Math.floor(n / 2), is O(log n): vanaf 1000 loopt die 9 keer, vanaf een miljoen 19 keer. Stappen na elkaar tel je op en de grotere term wint: een O(n)-lus gevolgd door een O(n²)-lus is samen O(n²).

// O(n): one pass
let total = 0;
for (const x of list) total += x;

// O(n²): every pair
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): halving
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Beste, gemiddelde en slechtste geval

Eén algoritme kan zich op verschillende invoer heel anders gedragen. Insertionsort is O(n) op een al gesorteerde lijst en O(n²) op een omgekeerde. Quicksort is gemiddeld O(n log n) en O(n²) met steeds slechte spillen. Als mensen één grote-O-waarde noemen zonder geval, bedoelen ze meestal het slechtste geval, omdat dat een garantie is: het algoritme doet nooit slechter. Grote O laat ook dingen weg. Het negeert constante factoren, dus voor kleine invoer kan een O(n²)-methode met heel eenvoudige stappen een O(n log n)-methode verslaan. Daarom schakelen veel echte sorteerroutines voor korte delen van de lijst over op insertionsort.