Veel algoritmes voor één probleem
Een algoritme is een reeks exacte stappen om een probleem op te lossen. De meeste problemen kun je met meer dan één algoritme oplossen. Om bijvoorbeeld een naam in een lijst te vinden, kun je elke naam controleren, of (als de lijst gesorteerd is) de lijst steeds in tweeën delen.
Beide geven het juiste antwoord. Het verschil is de efficiëntie: hoeveel werk en geheugen elk algoritme nodig heeft. Een goede programmeur kiest het algoritme dat snel blijft als de data groot wordt.
Algoritmes vergelijken op tijd
Meten met een stopwatch is niet eerlijk: op een snelle computer lijkt een traag algoritme goed. Daarom tellen we basisstappen (vergelijkingen, verwisselingen, optellingen) als functie van de invoergrootte n.
Beste, gemiddelde en slechtste geval
Het beste geval is de gelukkigste invoer (13 zit in het eerste doosje: 1 stap). Het slechtste geval is de ongelukkigste (13 zit er niet in: n stappen). Meestal noemen we het slechtste geval, want dat is een belofte: het algoritme is nooit trager dan dit.
Tijdcomplexiteit en ruimtecomplexiteit
Tijdcomplexiteit zegt hoe het aantal stappen groeit met n. Ruimtecomplexiteit zegt hoe het extra geheugen groeit met n. Mergesort is snel maar heeft extra geheugen nodig; bubblesort heeft bijna geen extra geheugen nodig maar is traag.
Big O-notatie
Big O beschrijft de groeisnelheid en negeert kleine details. We houden alleen de grootste term over en laten vaste getallen weg: 3n² + 5n + 2 wordt O(n²), want bij grote n is het n²-deel bijna alles.
| Big O | Naam | n = 16 | n = 1000 | Voorbeeld |
|---|---|---|---|---|
| O(1) | constant | 1 | 1 | item 5 van een rij lezen |
| O(log n) | logaritmisch | 4 | ongeveer 10 | binair zoeken |
| O(n) | lineair | 16 | 1000 | lineair zoeken, het grootste getal vinden |
| O(n log n) | n log n | 64 | ongeveer 10.000 | mergesort |
| O(n²) | kwadratisch | 256 | 1.000.000 | bubblesort, geneste lussen |
Vuistregel voor code: één lus over n items is O(n); een lus in een lus is O(n²); het probleem elke keer halveren is O(log n).
Efficiëntie van lineair en binair zoeken
Lineair zoeken controleert items één voor één. Slechtste geval: n vergelijkingen, dus O(n). Het werkt op elke lijst, gesorteerd of niet.
Binair zoeken heeft een gesorteerde lijst nodig. Kijk naar het middelste item; is het te groot, gooi dan de rechterhelft weg, anders de linkerhelft. Elke stap halveert de lijst, dus het slechtste geval is ongeveer log₂ n + 1 vergelijkingen: O(log n). Bij 1.000.000 items zijn dat ongeveer 20 stappen in plaats van 1.000.000.
Efficiëntie van sorteeralgoritmes
Bubblesort, insertion sort en selection sort gebruiken een lus in een lus, dus ze hebben ongeveer n²/2 vergelijkingen nodig: O(n²). Insertion sort is in het beste geval O(n) (een lijst die al gesorteerd is).
Mergesort halveert de lijst ongeveer log₂ n keer en doet op elk niveau ongeveer n werk: O(n log n). Het heeft O(n) extra geheugen nodig.
Binair zoeken heeft een gesorteerde lijst nodig. Zoek je maar één keer, dan kost eerst sorteren (n log n) meer dan één lineaire zoekactie (n). Zoek je vaak, dan loont het om één keer te sorteren.
Voorwaarden, nawaarden en valkuilen bij recursie
Een voorwaarde vooraf (precondition) is wat waar moet zijn voordat het algoritme begint (binair zoeken: de lijst is gesorteerd). Een voorwaarde achteraf (postcondition) is wat beloofd wordt als het klaar is (sorteren: elk item is kleiner dan of gelijk aan het volgende). Als je ze opschrijft, kun je een algoritme makkelijker testen en bewijzen.
Recursie betekent dat een functie zichzelf aanroept voor een kleiner probleem. Veelgemaakte fouten:
- Geen basisgeval, of een basisgeval dat nooit wordt bereikt: de aanroepen stoppen nooit (stack overflow).
- Het probleem wordt bij elke aanroep niet kleiner.
- Hetzelfde werk herhalen: een simpele recursieve Fibonacci roept fib(3) steeds opnieuw aan, dus het groeit als O(2ⁿ). Antwoorden opslaan (memoisatie) maakt het O(n).
- Heel diepe recursie gebruikt veel geheugen, één stackframe per aanroep.
Probeer het: laat twee zoekmethodes racen
Schrijf de getallen 1 tot 32 op papiertjes en leg ze op volgorde met de achterkant boven. Laat een vriend een geheim getal kiezen. Zoek eerst één voor één en tel hoeveel papiertjes je omdraait. Zoek daarna door steeds het middelste papiertje om te draaien. Herhaal dit 5 keer. Welke methode had nooit meer dan 6 beurten nodig? Controleer het met de schuifregelaar in de laatste 3D-stap (n = 32: log₂ 32 = 5).
Belangrijke formules en begrippen
- Lineair zoeken: slechtste geval n vergelijkingen → O(n)
- Binair zoeken: slechtste geval ongeveer log₂ n + 1 vergelijkingen → O(log n)
- Bubble / insertion / selection sort: ongeveer n(n − 1)/2 vergelijkingen → O(n²)
- Mergesort: ongeveer n log₂ n vergelijkingen → O(n log n)
- Big O-regel: houd de grootste term, laat constanten weg (5n² + 3n → O(n²))
- n verdubbelen: O(1) gelijk, O(log n) +1, O(n) ×2, O(n²) ×4
Uitgewerkte voorbeelden
1. Een lijst heeft 50 namen. Hoeveel vergelijkingen heeft lineair zoeken nodig in het beste en in het slechtste geval?
Beste geval: de naam staat vooraan → 1 vergelijking. Slechtste geval: de naam staat achteraan of ontbreekt → 50 vergelijkingen. Lineair zoeken is O(n).
2. Hoeveel vergelijkingen heeft binair zoeken maximaal nodig voor een gesorteerde lijst van 1024 items?
Elke stap halveert de lijst: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Dat zijn 10 keer halveren, plus de laatste controle: maximaal 11 vergelijkingen (log₂ 1024 = 10).
3. Geef de Big O van f(n) = 4n² + 10n + 7.
Houd de grootste term (4n²) en laat de constante 4 weg: O(n²).
4. Een lus laat i lopen van 1 tot n, en daarin laat een andere lus j lopen van 1 tot n. Hoe vaak wordt de binnenste regel uitgevoerd?
n keer voor elk van de n waarden van i: n × n = n². Tijdcomplexiteit O(n²).
5. Een O(n²)-programma sorteert 1000 items in 2 seconden. Ongeveer hoe lang duurt het voor 3000 items?
n wordt 3 keer zo groot, dus n² wordt 3² = 9 keer zo groot: ongeveer 2 × 9 = 18 seconden.
6. Vergelijk bubblesort en mergesort voor n = 1000 items.
Bubblesort: ongeveer n²/2 = 500.000 vergelijkingen. Mergesort: ongeveer n log₂ n = 1000 × 10 = 10.000. Mergesort doet ongeveer 50 keer minder werk, maar heeft extra geheugen nodig.
Veelgemaakte fouten
- Snelheid alleen meten met een stopwatch op één computer. Tel liever stappen tegenover n.
- Binair zoeken gebruiken op een ongesorteerde lijst. De voorwaarde vooraf is een gesorteerde lijst.
- Constanten in Big O houden, bijvoorbeeld O(2n) schrijven. Dat is gewoon O(n).
- Een recursieve functie schrijven zonder basisgeval, of een die het probleem niet kleiner maakt.