Bästa, sämsta & genomsnittsfallet
Tre sätt att mäta en algoritm
Varje algoritms kostnad beror på dess inmatning. Två inmatningar av samma storlek kan ge väldigt olika körtider. Komplexitetsanalys formaliserar tre perspektiv på denna variation.
Bästa fall — Ω (Omega): den inmatning som får algoritmen att slutföra snabbast. För linjär sökning över en lista med N objekt: Ω(1) — målet är på första positionen. En jämförelse, klart.
Sämsta fall — O (Big O): den inmatning som får algoritmen att slutföra långsammast. För linjär sökning: O(N) — målet är sist i listan, eller förekommer inte alls. Varje element kräver granskning.
Genomsnittsfallet — Θ (Theta): förväntad kostnad över alla möjliga inmatningar, förutsatt enhetlig fördelning. För linjär sökning där målet är lika sannolikt att uppta någon av N-positionerna: Θ(N/2) = Θ(N). Konstanten 1/2 försvinner eftersom Theta uttrycker snäv asymptotisk tillväxt, inte exakta koefficienter.
Varför värsta fall dominerar
System måste hantera värsta fall. En databasfråga som i genomsnitt tar 10 ms men ibland tar 60 sekunder orsakar ett synligt fel för användaren. Ingenjörer designar för värsta-fall-gränser så att prestandan förblir förutsägbar oavsett inmatning. Analys av genomsnittsfallet har värde i probabilistiska inställningar, men analys av värsta fallet ger garantier.
Binär sökning - fallanalys
Binär sökning fungerar bara på sorterade matriser. Vid varje steg: jämför målet med elementet i mittpunkten. Om målet är lika med mittpunkten, returnera det. Om målet är mindre, återkursera på den vänstra hälften. Om det är större, återkursera på den högra hälften.
Varje jämförelse eliminerar hälften av de återstående kandidaterna.
Minnestillväxt & tid-rymd-kompromisser
Räkna minne, inte operationer
Tidskomplexitet mäter antalet operationer som en algoritm utför. Rymdkomplexitet mäter det extra minne som den allokerar bortom dess inmatning. Båda spelar roll i produktionssystem: en snabb algoritm som allokerar O(N²) minne kommer att sluta på en server.
O(1) rymd: konstant extra minne oavsett N. En in-place-sortering (t.ex. insättningssortering) byter elementen inuti den ursprungliga matrisen. Den använder en handfull temporära variabler — O(1) oavsett hur stor matrisen är.
O(N) rymd: minne proportionellt mot indatastorlek. Att skapa en kopia av en N-elements matris kräver N platser. Att bygga en hash-uppsättning från en lista med N strängar lagrar upp till N poster.
O(N²) rymd: minne proportionellt mot N². Att bygga en N×N-närliggande matris för en graf med N hörn kräver N² celler. Vid N = 10 000 hörn är det 10^8 poster — hundratals megabyte för ett enkelt booleskt rutnät.
Tid-rymd-kompromisser
En av de grundläggande dragen i algoritmdesign: byta rymd mot tid, eller tid mot rymd.
Hash-tabeller använder O(N) extra rymd för att uppnå O(1)-sökning. Utan hash-tabellen uppnår en genomsökning av en lista O(N)-sökning med O(1) extra rymd. Hash-tabellen betalar minne för att köpa hastighet.
Memoization lagrar tidigare beräknade resultat (O(N) eller mer rymd) för att undvika att omberäkna dem. Rekursiv Fibonacci utan memoization körs i O(2^N) tid. Med memoization: O(N) tid och O(N) rymd. Ryminvesteringen minskar tiden exponentiellt.
Hash-ordbok mot sorterad lista
Jämför två strategier för att räkna ordförekomster i ett dokument med N ord:
Strategi A: en ordbok (hash-karta). Infoga varje ord; öka dess räkning.
Strategi B: underhålla en sorterad lista över sedda ord; använd binär sökning för att kontrollera medlemskap före infogning.
Amorterad analys: Sprida kostnaden
När enstaka utgifter inte förstör genomsnittsprestanda
Vissa operationer är ibland dyra men billiga i genomsnitt över en sekvens. Amorterad analys beräknar den genomsnittliga kostnaden per operation över hela sekvensen — inte värsta-fall-kostnaden för en enda operation.
Dynamisk matris (Python-lista, Java ArrayList): börjar med kapacitet 1. Vid full kapacitet fördubblar den. Att fördubbla kopierar alla befintliga element: O(N) arbete för en append. Men fördubblingar är sällsynta. Efter N totala tillägg, hur många totala kopieringsoperationer ägde rum?
Fördubblingar sker vid storlekar 1, 2, 4, 8, ..., N/2. Kopieringsräkningar: 1 + 2 + 4 + ... + N/2. Detta är en geometrisk serie som summerar till N − 1 totala kopior över alla N tillägg. Genomsnittskopior per tillägg: (N − 1) / N < 1, så O(1) amorterad per tillägg trots O(N) värsta-fall-kostnad per fördubbla.
Varför amorterad analys spelar roll
Ett system som ibland pausar för att ändra storlek, ombalansera eller kompaktera en struktur kan verka ha alarmerande värsta-fall-enskilda operationer. Amorterad analys avslöjar att alarmet är falskt: de sällsynta dyra händelserna betalas för av de många billiga. Att förstå amorterad kostnad förhindrar överkonstruktion: att lägga till komplexitet för att undvika en sällan O(N)-operation som bara bidrar O(1) amorterad är bortkastat arbete.
Fördjupning: Unhamming-kursen tillämpar komplexitetsanalys på verkliga fel i produktionsprogramvara. Se Det saknade kapitlet: Algoritmisk komplexitet & MOAD-0001: The Sedimentary Defect.
Amorterad hash-tabell-infogning
En hash-tabell börjar tom och fördubblar kapaciteten när lastfaktorn överskrider 0,75. Infogning av 1 000 element utlöser exakt 10 fördubblingar vid kapaciteter 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.