ZAČÁTKYNÁVODYOOPDOKUMENTACE
Handledning/
Algoritmer

Algoritmernas komplexitet

03. 08. 2021

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:

Související články

1.
4.