Best, Worst, & Gemiddeld Geval
Drie Manieren om een Algoritme te Meten
De kosten van elk algoritme hangen af van zijn invoer. Twee invoerwaarden van dezelfde grootte kunnen vervaagde uitvoeringstijden produceren. Complexiteitsanalyse formaliseert drie perspectieven op die variatie.
Beste geval — Ω (Omega): de invoer die het algoritme het snelst laat afgerond worden. Voor lineaire zoektocht over een lijst van N items: Ω(1) — het doelwit bevindt zich in de eerste positie. Een vergelijking, gedaan.
Slechtste geval — O (Big O): de invoer die het algoritme het langzaamst laat afgerond worden. Voor lineaire zoektocht: O(N) — het doelwit bevindt zich aan het einde van de lijst, of verschijnt niet. Elk element vereist inspectie.
Gemiddelde geval — Θ (Theta): verwachte kosten over alle mogelijke invoer, met de veronderstelling van een gelijke verdeling. Voor lineaire zoektocht met het doelwit evenwaarschijnlijk om elke van de N posities te bezetten: Θ(N/2) = Θ(N). Het constante 1/2 valt weg omdat Theta strakke asymptotische groei, niet exacte factoren beschrijft.
Waarom Slechtste Geval Overheerst
Systemen moeten het slechtste geval aangaan. Een databasequery die gemiddeld 10 ms duurt, maar af en toe 60 seconden kost, produceert een zichtbare fout voor de gebruiker. Ingenieurs ontwerpen voor de bovengrens van de uitvoeringstijd, zodat de prestaties voorspelbaar blijven ongeacht de invoer. Gemiddelde gevalanalyse heeft waarde in probabilistische omgevingen, maar analyse van het slechtste geval geeft garanties.
Analyse van het Geval voor Binair Zoeken
Binair zoeken werkt alleen op gesorteerde arrays. Bij elke stap: vergelijk het doelwit met het element op de middenpunt. Als het doelwit gelijk is aan het midden, retourneer het. Als het doelwit kleiner is, herhaal de recursie op de linker helft. Als groter, herhaal de recursie op de rechter helft.
Elke vergelijking verwijdert de helft van de overgebleven kandidaten.
Groei van geheugen, niet van operaties
Tellen van geheugen, niet van operaties
Tijdcomplexiteit meet het aantal uitgevoerde operaties van een algoritme. Ruimtecomplexiteit meet het extra geheugen dat het toewijst bovenop zijn invoer. Beide tellen 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 sort (bijv. insorteer sort) wisselt elementen binnen de oorspronkelijke array. Het gebruikt een handjevol tijdelijke variabelen - O(1) ongeacht de grootte van de array.
O(N) ruimte: geheugen evenredig aan de grootte van de invoer. Het maken van een kopie van een N-element array vereist N cellen. Het bouwen van een hash set van een lijst van N strings slaat op tot N entries.
O(N²) ruimte: geheugen evenredig aan N². Het bouwen van een N×N buurmatrix voor een grafiek met N knopen vereist N² cellen. Bij N = 10.000 knopen is dat 10^8 entries - honderden megabytes voor een eenvoudig booleaanse raster.
Tijd-ruimte handelswijze
Een van de fundamentele zetten in algoritme ontwerp: ruil ruimte voor tijd, of tijd voor ruimte.
Hash tabellen gebruiken O(N) extra geheugen om O(1) lookup te bereiken. Zonder de hash tabel, een scan over een lijst bereikt O(N) lookup met O(1) extra geheugen. De hash tabel betaalt geheugen om snelheid te kopen.
Memoisatie slaat voormalig berekende resultaten (O(N) of meer geheugen) op om herberekening te voorkomen. Recursieve Fibonacci zonder memoisatie loopt in O(2^N) tijd. Met memoisatie: O(N) tijd en O(N) ruimte. De investering in ruimte verkleint de tijd exponentieel.
Hash Dictionary vs Sorted List
Vergelijking van twee strategieën voor het tellen van woordvoorkomens in een document van N woorden:
Strategie A: een dictionary (hashmap). Voeg elk woord toe; verhoog zijn teller.
Strategie B: behoud een gesorteerde lijst van gezien woorden; gebruik een binair zoekalgoritme om lidmaatschap te controleren voordat je het toevoegt.
Amortiseerde Analyse: De Kosten Verspreiden
Wanneer Zeldzame Kosten De Gemiddelde Prestatie Niet Verwarrigt
Bepaalde operaties zijn af en toe duur maar voordelig gemiddeld over een reeks. Amortiseerde analyse berekent de gemiddelde kosten per operatie over de hele reeks - niet de ergste kosten van een enkele operatie.
Dynamische array (Python lijst, Java ArrayList): begint met een capaciteit van 1. Wanneer vol, verdubbelt de capaciteit. Verdubbelingen kopiëren alle bestaande elementen: O(N) werk voor één toevoegen. Maar verdubbelingen zijn zeldzaam. Na N totale toevoegingen, hoe vaak zijn er totale kopieoperaties plaatsgevonden?
Verdubbelingen vinden plaats bij capaciteiten 1, 2, 4, 8, ..., N/2. Kopietellingen: 1 + 2 + 4 + ... + N/2. Dit is een oneindige reeks die somt op tot N − 1 totale kopieën over alle N toevoegingen. Gemiddelde kopieën per toevoegen: (N − 1) / N < 1, dus O(1) amortiseerd per toevoegen ondanks O(N) ergste kosten per verdubbeling.
Waarom Amortiseerde Analyse Aanbevolen Wordt
Een systeem dat af en toe pauzeert om te resizen, te herstellen of een structuur te comprimeren, kan er schokkend uitzien in de ergste individuele operaties. Amortiseerde analyse toont aan dat de schrik onterecht is: de zeldzame dure gebeurtenissen worden betaald door de vele goedkope. Begrijpen van de amortiseerde kosten voorkomt over-engineering: het toevoegen van complexiteit om een zeldzame O(N) operatie te vermijden die slechts O(1) amortiseert, is verspilde moeite.
Dieper: De ongehamde cursus toepast complexiteitsanalyse op echte wereldfouten in productie software. Zie [Het missende hoofdstuk: Algoritmische complexiteit](/en/un/unhamming_algorithmic_complexity) & [MOAD-0001: De sedimentaire fout](/en/un/unhamming_moad_sedimentary).
Hash Table Amortized Insert
Een hash tabel begint leeg en verdubbelt de capaciteit wanneer de belastingfactor hoger is dan 0,75. Het inschrijven van 1.000 elementen triggerd exact 10 verdubbelingen met capaciteiten van 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.