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	n²	n²	1	Ja
Insättningssortering	n	n²	n²	1
Väljningssortering	n²	n²	n²	n²	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)	n²	log(n)	Nej
Shell sort	n log(n)	beror på sekvensen	n (log(n))²	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: