Varje komplexitetsklass ritar en kurva
Plotta kostnad mot indatastorlek
Sätt indatastorlek N på x-axeln. Sätt kostnad (operationer, tid) på y-axeln. Varje komplexitetsklass producerar en distinkt kurva. Du kan känna igen en algoritms tillväxttakt från formen på dess prestandakurva.
O(1) — platt horisontell linje. Funktionen f(N) = 1. Ingen lutning. Kostnad ändras aldrig oavsett N. Hashtabell-sökning: oavsett om tabellen innehåller 10 eller 10 000 000 element hoppar en hashberäkning till rätt bucket.
O(log N) — svag uppåtgående kurva, lutning som minskar. Vid N = 1 000 000: kostnad ≈ 20 operationer. Kurvan stiger brant vid små N, sedan plattas den ut. Varje fördubbling av N lägger till exakt en enhet kostnad.
O(N) — diagonal rak linje. Lutning = 1 (i asymptotisk mening). Kostnad växer med samma takt som N. Om N tredubblas tredubblas kostnad.
O(N log N) — brantare diagonal med svag uppåtgående krökning. Sitter ovanför O(N) men under O(N²). Logfaktorn lägger till en långsamt växande multiplikator till den linjära lutningen.
O(N²) — parabel som öppnar uppåt. Lutning ökar när N växer. Vid N = 10: kostnad = 100. Vid N = 100: kostnad = 10 000. Vid N = 1 000: kostnad = 1 000 000.
Gapet växer
Förhållandet O(N²) / O(N) = N. Gapet mellan parabeln och diagonalen vidgas när N växer. Vid N = 10: 10× gap. Vid N = 100: 100× gap. Vid N = 1 000: 1 000× gap. Vid N = 50 000: 50 000× gap. Gapet motsvarar alltid N.
Beräkning av skalningsgapet
En stor beroendegraff innehåller 50 000 paket (N = 50 000). En algoritm körs i O(N) tid. En annan körs i O(N²) tid. Vid detta N motsvarar förhållandet O(N²)/O(N) = N = 50 000.
Halving ett linjesegment
Binär sökning som upprepad halving
En sorterad array med N element bildar ett linjesegment av längd N. Binär sökning halverar upprepade gånger detta segment:
1. Peka på mittpunkten av det återstående segmentet.
2. Om mål < mittpunkt: höger halva försvinner. Rekursera på vänster halva.
3. Om mål > mittpunkt: vänster halva försvinner. Rekursera på höger halva.
4. Om mål = mittpunkt: klart.
Efter k halvningar har det återstående segmentet längd N / 2^k. Sökningen slutar när längden är 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Så binär sökning på N element kräver högst log₂N jämförelser.
Halving & fördubbling: två sidor av samma kurva
Halving och fördubbling är geometriska inverser. Exponentialkurvan 2^k och logaritmkurvan log₂N är reflektioner av varandra över linjen y = x.
Tänk på pappersveckning: ett ark börjar på 0,1 mm tjockt. Varje veckning fördubblar tjockleken. Efter 42 veckningar: 0,1 mm × 2^42 ≈ 439 804 km — bortom månen (384 400 km). Binär sökning kör inversen: börja med N element, varje steg halverar antalet, nå 1 element i log₂N steg.
Geometrin: halving är en självsimilär operation. Varje halving producerar två halvor som ser identiska ut strukturellt med helheten. Rekursion och logaritmer delar denna självsimilaritet.
Jämförelser & fördubblingar
En sorterad array innehåller 1 048 576 element. Notera: 1 048 576 = 2^20.
En hashfunktion som geometrisk map
Hashfunktion som funktion
En hashtabell mappar en nyckel till ett bucket med en hashfunktion:
bucket = hash(key) mod table_size
Detta är en funktion i strikt matematisk mening: den mappar en domän (alla möjliga nycklar) till ett värderum (bucket-index 0 till table_size − 1). Geometribilden: nycklar befinner sig i ett utrymme; buckets befinner sig i ett annat. Hashfunktionen projicerar nycklar på bucket-index.
O(1) sökning — direkt hopp, ingen sökning. Hashfunktionen beräknar bucket-indexet på konstant tid. Hoppa direkt till det bucketet. Ingen traversal, ingen jämförelseloop.
Belastningsfaktor. Vid belastningsfaktor 0,75 innehåller 75% av bucketen minst ett element. Över ~0,9 ökar kollisioner: två nycklar hashar till samma bucket och bildar en kedja av element inuti det bucketet. Sökning i en lång kedja försämras till O(N) i värsta fall.
Distributionskvalitet som geometri
En välfördelad hashfunktion sprider nycklar jämnt över alla buckets. Geometriskt: funktionens värderum täcker dess kodomän jämnt. Varje bucket tar emot ungefär N / table_size nycklar.
En dålig hashfunktion klustrar nycklar i ett fåtal buckets. Geometriskt: funktionens värderum kollapsar till en delmängd av kodomänen — de flesta nycklar mappar till samma få punkter. Återstående buckets sitter tomma.
Anslutning till MOAD-0001
Att ersätta en lista med en set fixar MOAD-0001 eftersom en set använder en hashtabell internt. O(N) lista-sökning → O(1) hashtabell-sökning. Geometriskt: linjär traversal längs en sekvens förvandlas till en direkt projektion via en funktion. Sekvensen försvinner; funktionen ersätter den.
Analys av en dåligt fördelad hash
En hashtabell har 1 000 buckets och 900 element (belastningsfaktor 0,9). En dålig hashfunktion skickar 500 av dessa element till samma bucket.