Algoritmernas komplexitet
Obsah článku
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 Více o autorovi
Autor článku pracuje jako seniorní vývojář a software architekt v Praze. Navrhuje a spravuje velké webové aplikace, které znáte a používáte. Od roku 2009 nabral bohaté zkušenosti, které tímto webem předává dál.
Rád vám pomůžu:
Články píše Jan Barášek © 2009-2022 | Kontakt | Mapa webu
Vue.js manual | Status | Aktualizováno: ... | sv
