Algoritmernas komplexitet
Varje algoritm har sin egen komplexitet, som kan uttryckas i matematisk notation. Denna översikt visar algoritmernas typiska komplexitet beroende på storleken på indata (dvs. antalet element som de arbetar med) och vilka typer av algoritmer som är lämpliga för vilken typ av uppgift.
I allmänhet finns det en bästa specialiserad algoritm för varje typ av problem. Ingen algoritm är alltid bäst och du måste alltid känna till ditt sammanhang.
Big O-notation
Big O-notationen används för att klassificera algoritmer efter hur deras körtids- eller minneskrav ökar med ökande storlek på indata.
Följande diagram visar de vanligaste tillväxtordningarna för algoritmer som anges i Big O-notation.
Nedan följer en förteckning över några av de vanligaste Big O-notationerna och en jämförelse av deras prestanda med avseende på olika storlekar på indata.
| Big O Notation | Komplexitet för 10 element | Komplexitet för 100 element | Komplexitet för 1000 element |
|---|---|---|---|
| O(1) | 1 | 1 | 1 |
| O(log N) | 3 | 6 | 9 |
| O(N) | 10 | 100 | 1000 |
| O(N log N) | 30 | 600 | 9000 |
| O(N^2) | 100 | 10000 | 1000000 |
| O(2^N) | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |
Komplexiteten hos datastrukturoperationer
| Datastruktur | Åtkomst | Sök | Infoga | Ta bort | Kommentera |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | n |
| Stack | n | n | n | n | n |
| Queue | n | n | n | n | n |
| Länkad lista | n | n | n | n | n |
| Hashtabell | - | n | n | n | n |
| Binary Search Tree | n | n | n | n | n |
| B-Tree | log(n) | log(n) | log(n) | log(n) | log(n) |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | log(n) |
| AVL Tree | log(n) | log(n) | log(n) | log(n) | log(n) |
| Bloom Filter | - | 1 | 1 | 1 | - |
Komplexitet hos sorteringsalgoritmer
| Algoritmens namn | Bäst | Medel | Sämst | Minne | Stabilt? | Kommentar |
|---|---|---|---|---|---|---|
| Bubbelsortering | n | n2 | n2 | 1 | Ja | |
| Insättningssortering | n | n2 | n2 | 1 | ||
| Väljningssortering | n2 | n2 | n2 | n2 | 1 | |
| Heap sort | n log(n) | n log(n) | n log(n) | n log(n) | 1 | |
| Merge sort | n log(n) | n log(n) | n log(n) | n log(n) | n | Ja |
| Snabbsortering | n log(n) | n log(n) | n2 | log(n) | Nej | |
| Shell sort | n log(n) | beror på sekvensen | n (log(n))2 | 1 | ||
| Räkningssortering | n + r | n + r | n + r | n + r | n + r | n + r |
| Radix-sortering | n * k | n * k | n * k | n * k | n + k | Ja |
Jan Barášek Mer om författaren
Författaren arbetar som senior utvecklare och mjukvaruarkitekt i Prag. Han utformar och förvaltar stora webbprogram som du känner till och använder. Sedan 2009 har han skaffat sig en stor erfarenhet som han förmedlar via denna webbplats.
Jag hjälper gärna till:
Kontakt