Složitost algoritmů

📅   03. 08. 2021

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 n2 n2 1 Ano
Insertion sort n n2 n2 1 Ano
Selection sort n2 n2 n2 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) n2 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))2 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
Nechte si posílat nové články do mailu:

Jan Barášek     Více o autorovi

Autor článku podniká jako senior software architekt v Praze. Navrhuje a spravuje velké webové ekosystémy, které znáte a používáte. Během mnoha let nabral hluboké zkušenosti, které tímto webem předává dál.

Rád vám pomůžu:

Kontakt Konzultace a služby