Beste, Slechtste en Gemiddelde Case
Drie Manieren om een Algoritme te Meten
De kosten van elk algoritme hangen af van de invoer. Twee invoeren van dezelfde grootte kunnen wild verschillende runtimes produceren. Complexiteitsanalyse formaliseert drie perspectieven op die variatie.
Beste case — Ω (Omega): de invoer die het algoritme het snelst laat eindigen. Voor lineair zoeken over een lijst van N items: Ω(1) — het doel neemt de eerste positie in. Één vergelijking, klaar.
Slechtste case — O (Big O): de invoer die het algoritme het langzaamst laat eindigen. Voor lineair zoeken: O(N) — het doel zit het laatste in de lijst, of bestaat helemaal niet. Elk element vereist inspectie.
Gemiddelde case — Θ (Theta): verwachte kosten over alle mogelijke invoeren, aangenomen uniforme verdeling. Voor lineair zoeken waarbij het doel even waarschijnlijk is op elk van N posities: Θ(N/2) = Θ(N). De constante 1/2 valt weg omdat Theta nauwe asymptotische groei uitdrukt, niet exacte coëfficiënten.
Waarom Slechtste Case Domineert
Systemen moeten het slechtste geval aankunnen. Een databasequery die gemiddeld 10 ms duurt maar af en toe 60 seconden kost, produceert een voor de gebruiker zichtbare mislukking. Ingenieurs ontwerpen voor worst-case grenzen zodat de prestaties voorspelbaar blijven ongeacht de invoer. Gemiddelde-case analyse heeft waarde in probabilistische instellingen, maar worst-case analyse geeft garanties.
Case-analyse Binair Zoeken
Binair zoeken werkt alleen op gesorteerde arrays. Bij elke stap: vergelijk het doel met het element op het middelpunt. Als het doel gelijk is aan het middelpunt, retourneer het. Als het doel kleiner is, herhaal recursief op de linkerhelft. Als groter, herhaal op de rechterhelft.
Elke vergelijking elimineert de helft van de resterende kandidaten.
Geheugtengroei & Tijd-Ruimte Afwegingen
Geheugen Tellen, Niet Operaties
Tijdcomplexiteit meet het aantal operaties dat een algoritme uitvoert. Ruimtecomplexiteit meet het extra geheugen dat het toewijst voorbij zijn invoer. Beide zijn belangrijk in productiesystemen: een snel algoritme dat O(N²) geheugen toewijst zal een server uitputten.
O(1) ruimte: constant extra geheugen ongeacht N. Een in-place sortering (bijv. insertion sort) verwisselt elementen in de originele array. Het gebruikt een handvol tijdelijke variabelen — O(1) ongeacht hoe groot de array.
O(N) ruimte: geheugen proportioneel tot invoergrootte. Een kopie maken van een N-element array vereist N slots. Een hash-set bouwen van een lijst van N strings slaat tot N vermeldingen op.
O(N²) ruimte: geheugen proportioneel tot N². Een N×N adjacency matrix bouwen voor een graaf met N vertices vereist N² cellen. Bij N = 10.000 vertices zijn dat 10^8 vermeldingen — honderden megabytes voor een eenvoudig boolean grid.
Tijd-Ruimte Afwegingen
Een van de fundamentele zetten in algoritmeontwerp: handel ruimte in voor tijd, of tijd voor ruimte.
Hash-tabellen gebruiken O(N) extra ruimte om O(1) opzoeking te bereiken. Zonder de hash-tabel bereikt een scan over een lijst O(N) opzoeking met O(1) extra ruimte. De hash-tabel betaalt geheugen om snelheid te kopen.
Memoization slaat eerder berekende resultaten op (O(N) of meer ruimte) om ze niet opnieuw te hoeven berekenen. Recursieve Fibonacci zonder memoization loopt in O(2^N) tijd. Met memoization: O(N) tijd en O(N) ruimte. De ruimteinvestering krimpt tijd exponentieel.
Hash-woordenboek versus Gesorteerde Lijst
Vergelijk twee strategieën voor het tellen van woordvoorkomens in een document van N woorden:
Strategie A: een woordenboek (hash map). Voeg elk woord in; verhoog het aantal.
Strategie B: behoud een gesorteerde lijst van waargenomen woorden; gebruik binair zoeken om lidmaatschap te controleren voordat je invoegt.
Gemitigeerde Analyse: Kosten Spreiden
Wanneer Af en toe Dure Kosten Gemiddelde Prestaties niet Ruïneren
Enkele operaties zijn af en toe duur maar goedkoop gemiddeld over een reeks. Gemitigeerde analyse berekent de gemiddelde kosten per operatie over de gehele reeks — niet de worst-case kosten van een enkele operatie.
Dynamische array (Python list, Java ArrayList): begint met capaciteit 1. Wanneer vol, verdubbelt capaciteit. Verdubbeling kopieert alle bestaande elementen: O(N) werk voor één append. Maar verdubbelingen zijn zeldzaam. Na N totaal appends, hoeveel totale copy operaties zijn er voorgekomen?
Verdubbelingen gebeuren bij grootten 1, 2, 4, 8, ..., N/2. Copy aantallen: 1 + 2 + 4 + ... + N/2. Dit is een geometrische reeks som tot N − 1 totaal kopieën over alle N appends. Gemiddelde kopieën per append: (N − 1) / N < 1, dus O(1) gemitigeerd per append ondanks O(N) worst-case kosten per verdubbeling.
Waarom Gemitigeerde Analyse Belangrijk Is
Een systeem dat af en toe pauzeert om een structuur te vergroten, opnieuw in balans te brengen, of samen te persen, mag alarmerend worst-case individuele operaties lijken te hebben. Gemitigeerde analyse onthult dat het alarm onwaar is: de zeldzame dure gebeurtenissen worden betaald door de vele goedkope. Inzicht in gemitigeerde kosten voorkomt over-engineering: complexiteit toevoegen om een zeldzame O(N) operatie te vermijden die slechts O(1) gemitigeerd bijdraagt, is verspilde werk.
Dieper gaan: De unhamming cursus past complexiteitsanalyse toe op real-world defecten in productiesoftware. Zie Het Ontbrekende Hoofdstuk: Algoritmische Complexiteit & MOAD-0001: Het Sedimentaire Defect.
Gemitigeerde Insert in Hash-tabel
Een hash-tabel begint leeg en verdubbelt capaciteit wanneer load factor 0,75 overschrijdt. Het invoegen van 1.000 elementen triggert exact 10 verdubbelingen bij capaciteiten 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.