Algoritmy

Složitost algoritmů

03. 08. 2021

Obsah článku

Každý algoritmus má svojí složitost, kterou můžeme vyjádřit matematickým zápisem. Tento přehled ukazuje typické složitosti algoritmů podle velikosti vstupních dat (tj. počtu prvků, s kterými pracují) a jaké typy algoritmů se hodí podle typu úlohy.

Obecně platí, že pro každý typ problému existuje nejlepší specializovaný algoritmus. Žádný algoritmus není univerzálně nejlepší, a vždy musíte znát váš kontext.

Big O Notation

Big O Notation se používá ke klasifikaci algoritmů podle toho, jak s rostoucí velikostí vstupu roste jejich doba běhu nebo paměťové nároky.

Na následujícím grafu můžete najít nejčastější řády růstu algoritmů specifikovaných v notaci Big O.

Níže je uveden seznam některých nejpoužívanějších notací Big O a srovnání jejich výkonnosti vzhledem k různým velikostem vstupních dat.

Big O Notation	Složitost pro 10 elementů	Složitost pro 100 elementů	Složitost pro 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

Složitost operací datové struktury

Struktura dat	Přístup	Hledání	Vložení	Odebráné	Komentář
Array	1	n	n	n
Stack	n	n	1	1
Queue	n	n	1	1
Linked List	n	n	1	n
Hash Table	-	n	n	n	V případě dokonalé hashovací funkce bude složitost O(1)
Binary Search Tree	n	n	n	n	V případě vyváženého stromu složitost bude O(log(n)).
B-Tree	log(n)	log(n)	log(n)	log(n)
Red-Black Tree	log(n)	log(n)	log(n)	log(n)
AVL Tree	log(n)	log(n)	log(n)	log(n)
Bloom Filter	-	1	1	-	Při hledání jsou možné tzv. `false positives`

Složitost řadících algoritmů

Název algoritmu	Nejlepší	Průměrná	Nejhorší	Paměť	Stabilní?	Komentář
Bubble sort	n	n²	n²	1	Ano
Insertion sort	n	n²	n²	1	Ano
Selection sort	n²	n²	n²	1	Ne
Heap sort	n log(n)	n log(n)	n log(n)	1	Ne
Merge sort	n log(n)	n log(n)	n log(n)	n	Ano
Quick sort	n log(n)	n log(n)	n²	log(n)	Ne	Quicksort se obvykle provádí se složitostí O(log(n)) zásobníku.
Shell sort	n log(n)	závisí na posloupnosti	n (log(n))²	1	Ne
Counting sort	n + r	n + r	n + r	n + r	Ano	r - největší číslo v poli
Radix sort	n * k	n * k	n * k	n + k	Ano	k - délka nejdelšího klíče

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: