Algoritmernas komplexitet

📅   03. 08. 2021
👤   Jan Barášek

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