Složitost algoritmů
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 |
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:
Související články
Potřebujete poradit s PHP?
Nabízím trénink vývojářů, konzultace, školení a analýzu návrhových vzorů. Osobně v Praze nebo online.
Napište mi, pokud si nevíte rady.
Lektor: Jan Barášek
Články píše Jan Barášek © 2009-2024 | Kontakt | Mapa webu
Status | Aktualizováno: ... | cs