Asymptotická složitost je nástrojem k porovnávání efektivity algoritmů. Složitost vyjadřuje, jak roste náročnost algoritmu (doba výpočtu nebo potřebná paměť) s rostoucím množstvím vstupních dat. Dobu výpočtu lze definovat jako počet všech elementárních operací, které algoritmus vykoná při zpracování daného vstupu. Každá tato operace musí být dokončena v konstantním čase a patří mezi ně například základní aritmetické operace, porovnání dvou hodnot či přiřazení.
Protože je algoritmus obecný a jeho konkrétní implementace se mohou více či méně lišit, je k jejich srovnávání nutné použít metodu „odolnou“ vůči specifikám jednotlivých platforem. Především se složitost počítá tzv. asymptoticky a během „výpočtu“ se zanedbávají nepodstatné členy (např. aditivní a multiplikativní konstanty).
Asymptotickou složitost si lze představit jako „řád růstu“, tedy „zařazení“ algoritmu do několika základních kategorií (lineární, exponenciální, logaritmická…).
Množina Omega funkce f je množina všech funkcí, které mají „stejný“ nebo „vyšší“ řád růstu jako funkce f.
Prohlásíme-li, že složitost algoritmu leží v množině Omega funkce f, znamená to, že bude náročnost algoritmu růst vždy stejně nebo více než funkce f. Notaci Omega lze tedy chápat jako vyjádření „nejlepšího případu“.
Čteme: Funkce f je funkcí g ohraničena zdola (až na konstantu).
€€ \begin{align*} &f(x) \in \Omega(g(x)): \\ &\exists C, x_0;\; C > 0; \\ &\forall (x>x_0) \; |C \cdot g(x)| \leq |f(x)| \end{align*} €€Množina Omikron funkce f je množina všech funkcí, které mají „stejný“ nebo „nižší“ řád růstu jako funkce f.
Prohlásíme-li, že složitost algoritmu leží v množině Omikron funkce f, znamená to, že bude náročnost algoritmu růst vždy stejně nebo méně než funkce f. Notaci Omikron tedy lze chápat jako vyjádření „nejhoršího případu“.
Čteme: Funkce f je funkcí g ohraničena shora (až na konstantu).
€€ \begin{align*} &f(x) \in O(g(x)): \\ &\exists C, x_0;\; C > 0; \\ &\forall (x>x_0) \; |f(x)| \leq |C \cdot g(x)| \end{align*} €€Množina Theta funkce f je množina všech funkcí, které mají „stejný“ řád růstu jako funkce f.
Prohlásíme-li, že složitost algoritmu leží v množině Theta funkce f, znamená to, že bude náročnost algoritmu růst vždy stejně jako funkce f.
U některých algoritmů nelze složitost pomocí množiny Theta specifikovat.
Čteme: Funkce f je funkcí g ohraničena z obou stran (až na konstantu).
€€ \begin{align*} &f(x) \in \Theta(g(x)): \\ &\exists C, C';\; C,C' > 0; \\ &\forall (x>x_0) \; |C \cdot g(x)| \leq |f(x)| \leq |C' \cdot g(x)| \end{align*} €€Počet operací je pro libovolně velká vstupní data zhruba stejný.
€€ O(1) €€Náročnost algoritmu se zvyšuje podobně jako velikost vstupních dat.
€€ O(n) €€Náročnost algoritmu roste jako druhá mocnina velikosti vstupních dat.
€€ O(n^2) €€