Složitost algoritmů
Z Wikipedie, otevřené encyklopedie
Složitost algoritmu vyjadřuje spotřebu výpočetních prostředků (např. paměti nebo výpočetního času, vyjádřeného jako počet provedených kroků či instrukcí) v závislosti na velikosti vstupních dat. Jako krok algoritmu se obvykle považuje činnost, kterou lze provést v konstantním časovém úseku (např. porovnání dvou čísel, přiřazení do jednoduché proměnné, atd., tedy nikoli operace s celými poli čísel, řazení čísel a další náročnější operace).
Obvykle se zapisuje jako O(f(n)).
Tento zápis znamená, že náročnost algoritmu je menší než a + b * f(n) , kde a a b jsou vhodně zvolené konstanty a n je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, zajímá nás jen chování funkce pro velké hodnoty n.
Algoritmy můžeme podle f(n) rozřadit do tříd.
Pokud je f(n) polynom, hovoříme o polynomiálně omezených algoritmech. Takové problémy, které řeší nějaký polynomiální algoritmus, patří do tzv. třídy P.
Pokud pro daný problém neexistuje polynomiálně omezený algoritmus, který řešení nalezne, ale existuje polynomiálně omezený algoritmus, který řešení ověří, hovoříme o nederministicky polynomiálních problémech. Problémy, které řeší nedeterministický algoritmus, patří do třídy NP (např. problém obchodního cestujícího, splnitelnost formule výrokové logiky a mnoho dalších).
Jednou z největších současných otevřených otázek teoretické informatiky je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz NP-úplnost).
[editovat] Porovnání složitostí
Obecně se říká, že problémy, pro které je znám algoritmus, který je spočte v nejvýše polynomiálním čase se nazývají výpočetně snadné, ostatní výpočetně složité.
Představu o složitosti problému dává následující tabulka, která popisuje počet instrukcí na zpracování vstupu o velikosti 1000
| Vstup délky 1 | Vstup délky 10 | Vstup délky 1000 | |
|---|---|---|---|
| o(ln10(x)), logaritmická složitost | < 1 | 1 | 3 |
| o(x), lineární složitost | 1 | 10 | 1000 |
| o(x3), kubická složitost | 1 | 10000 | 1000000000 |
| o(10x), exponenciealní složitost (NP-problémy) | 10 | 10000000000 | 101000 |
Existují i funkce, u nichž nelze složitost vůbec shora rozumně omezit. Příkladem budiž Ackermannova funkce.

