Algoritmernes kompleksitet

03. 08. 2021

Obsah článku

Hver algoritme har sin egen kompleksitet, som kan udtrykkes i matematisk notation. Denne oversigt viser algoritmernes typiske kompleksitet i forhold til størrelsen af inputdataene (dvs. antallet af elementer, de arbejder med), og hvilke typer algoritmer der egner sig til hvilken type opgave.

Generelt findes der en bedste specialiseret algoritme for hver type problem. Ingen algoritme er altid den bedste, og du skal altid kende din kontekst.

Big O Notation

Big O-notationen bruges til at klassificere algoritmer efter, hvordan deres løbetid eller hukommelseskrav stiger med stigende inputstørrelse.

Følgende skema viser de mest almindelige vækstordner for algoritmer, der er specificeret i Big O-notation.

Nedenfor er der en liste over nogle af de mest almindeligt anvendte Big O-notationer og en sammenligning af deres ydeevne med hensyn til forskellige inputdatastørrelser.

Big O Notation	Kompleksitet for 10 elementer	Kompleksitet for 100 elementer	Kompleksitet for 1000 elementer
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

Kompleksitet af datastrukturoperationer

Datastruktur	Adgang	Søg	Indsæt	Fjern	Kommentar
Array	1	n	n	n	n
Stack	n	n	n	n	n
Queue	n	n	n	n	n
Linked List	n	n	n	n	n
Hash Table	-		n	n	n
Binary Search Tree	n	n	n	n	n
B-Tree	log(n)	log(n)	log(n)	log(n)	log(n)
Rødt-sort træ	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

Sorteringsalgoritmers kompleksitet

Algoritmens navn	Bedste	Gennemsnitlig	Værste	Hukommelse	Stabil?	Kommentar
Bubble sort	n	n	n²	n²	n²	1
Insættelsessortering	n	n	n²	n²	n²	1
Selektionssortering	n²	n²	n²	n²	1
Heap sort	n log(n)	n log(n)	n log(n)	n log(n)	1
Sammenlægningssortering	n log(n)	n log(n)	n log(n)	n log(n)	n	Ja
Quick sort	n log(n)	n log(n)	n log(n)	n²	log(n)	Nej
Shell sort	n log(n)	afhænger af sekvensen	n (log(n))²	1
Tællesortering	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: