Elke Complexiteitsklasse Tekent een Curve
Zet Kosten tegen Invoergrootte uit
Zet invoergrootte N op de x-as. Zet kosten (bewerkingen, tijd) op de y-as. Elke complexiteitsklasse produceert een duidelijke curve. Je kunt de groeisnelheid van een algoritme herkennen aan de vorm van zijn prestatiecurve.
O(1) — vlakke horizontale lijn. De functie f(N) = 1. Geen helling. Kosten veranderen nooit ongeacht N. Hash-tabelopzoeking: of de tabel nu 10 of 10.000.000 elementen bevat, één hash-berekening springt naar de juiste bucket.
O(log N) — zachte opwaartse curve, helling afnemend. Bij N = 1.000.000: kosten ≈ 20 bewerkingen. De curve stijgt steil bij kleine N, dan vlakt af. Elke verdubbeling van N voegt precies één eenheid kosten toe.
O(N) — diagonale rechte lijn. Helling = 1 (in asymptotische zin). Kosten groeien met dezelfde snelheid als N. Als N verdrievoudigt, verdrievoudigen kosten.
O(N log N) — steilere diagonaal met lichte opwaartse kromming. Zit boven O(N) maar onder O(N²). De log-factor voegt een langzaam groeiende vermenigvuldiger toe aan de lineaire helling.
O(N²) — parabool die zich naar boven opent. Helling neemt toe naarmate N groeit. Bij N = 10: kosten = 100. Bij N = 100: kosten = 10.000. Bij N = 1.000: kosten = 1.000.000.
De Groeiende Kloof
De verhouding O(N²) / O(N) = N. De kloof tussen de parabool en de diagonaal wordt breder naarmate N groeit. Bij N = 10: 10× kloof. Bij N = 100: 100× kloof. Bij N = 1.000: 1.000× kloof. Bij N = 50.000: 50.000× kloof. De kloof is altijd gelijk aan N.
De Schaalkloof Berekenen
Een grote afhankelijkheidsgrafiek bevat 50.000 pakketten (N = 50.000). Één algoritme loopt in O(N)-tijd. Een tweede loopt in O(N²). Bij deze N is de verhouding O(N²)/O(N) = N = 50.000.
Een Lijnstuk Halveren
Binair Zoeken als Herhaalde Halvering
Een gesorteerde array van N elementen vormt een lijnstuk van lengte N. Binair zoeken halveert dit segment herhaaldelijk:
1. Wijs naar het middelpunt van het resterende segment.
2. Als doel < middelpunt: de rechterkant verdwijnt. Herhaal op de linkerkant.
3. Als doel > middelpunt: de linkerkant verdwijnt. Herhaal op de rechterkant.
4. Als doel = middelpunt: klaar.
Na k halveringen heeft het resterende segment lengte N / 2^k. De zoekopdracht eindigt wanneer die lengte gelijk is aan 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Dus binair zoeken op N elementen vereist hooguit log₂N vergelijkingen.
Halvering & Verdubbeling: Twee Zijden van Dezelfde Curve
Halvering en verdubbeling zijn geometrische inverses. De exponentiële curve 2^k en de logaritmische curve log₂N zijn reflecties van elkaar over de lijn y = x.
Denk aan papierplooien: een vel begint 0,1 mm dik. Elke plooi verdubbelt de dikte. Na 42 plooien: 0,1 mm × 2^42 ≈ 439.804 km — verder dan de maan (384.400 km). Binair zoeken doet het omgekeerde: begin met N elementen, elk stap halveert het aantal, bereik 1 element in log₂N stappen.
De geometrie: halvering is een zelf-gelijke operatie. Elke halvering produceert twee helften die structureel identiek lijken aan het geheel. Recursie en logaritmen delen deze zelf-gelijkenis.
Vergelijkingen & Verdubbelingen
Een gesorteerde array bevat 1.048.576 elementen. Opmerking: 1.048.576 = 2^20.
Een Hash-functie als Geometrische Afbeelding
Hash-functie als Functie
Een hash-tabel wijst een sleutel toe aan een bucket met behulp van een hash-functie:
bucket = hash(key) mod table_size
Dit is een functie in strikte wiskundige zin: het wijst een domein (alle mogelijke sleutels) toe aan een bereik (bucket-indexen 0 tot tabel_grootte − 1). Het geometrische beeld: sleutels innemen één ruimte; buckets nemen een ander in. De hash-functie projecteert sleutels op bucket-indexen.
O(1)-opzoeking — rechtstreekse sprong, geen zoekopdracht. De hash-functie berekent de bucket-index in constant tijd. Spring rechtstreeks naar die bucket. Geen traversal, geen vergelijkingslus.
Belastingsfactor. Bij belastingsfactor 0,75 bevatten 75% van de buckets minstens één element. Boven ~0,9 nemen botsingen toe: twee sleutels hashen naar dezelfde bucket, formeren een keten van elementen in die bucket. Opzoeking in een lange keten verslechtert tot O(N) in het slechtste geval.
Distributiekwaliteit als Geometrie
Een goed verspreide hash-functie verspreidt sleutels uniform over alle buckets. Geometrisch: het bereik van de functie dekt zijn codomein gelijkmatig. Elke bucket ontvangt ongeveer N / tabel_grootte sleutels.
Een slechte hash-functie clustert sleutels in enkele buckets. Geometrisch: het bereik van de functie valt in tot een subset van het codomein — de meeste sleutels wijzen naar dezelfde paar punten. De resterende buckets zijn leeg.
Verbinding met MOAD-0001
Een lijst vervangen door een verzameling verhelpt MOAD-0001 omdat een verzameling intern een hash-tabel gebruikt. O(N)-lijstsoek → O(1)-hash-tabelopzoeking. Geometrisch: lineaire doorvoering langs een reeks transformeert in een rechtstreekse projectie via een functie. De reeks verdwijnt; de functie vervangt het.
Een Slecht Verspreide Hash Analyseren
Een hash-tabel heeft 1.000 buckets en 900 elementen (belastingsfactor 0,9). Een slechte hash-functie stuurt 500 van die elementen naar dezelfde bucket.