K porovnávání asymptotického chování39 členů posloupností se často využívá Landauova symbolika (též známá pod označením \(\mathcal{O}\)-notace; Edmund Landau, německý matematik, 1877 – 1938). S touto symbolikou se velmi často setkáte při vyjadřování časových a paměťových složitostí algoritmů40.
V této krátké kapitole zavedeme dva základní asymptotické vztahy, vlnovku \(\sim\) a velké \(\mathcal{O}\). Přesná definice těchto symbolů je následující.
Nechť \((a_n)_{n=1}^\infty\) a \((b_n)_{n=1}^\infty\) jsou číselné posloupnosti. Řekneme, že
Jaký je význam těchto vztahů. Z definice by mělo být patrné, že jestliže \(a_n \sim b_n\), pak se pro velká \(n\) obě posloupnosti „chovají stejně“, jsou tzv. asymptoticky ekvivalentní. Speciálně platí, že pokud \(a_n \sim b_n\), pak \(\lim a_n = \alpha\) právě když \(\lim b_n = \alpha\).
Ačkoliv jsme relace nezavedli poznamenejme, že \(\sim\) je skutečně relací ekvivalence na množině všech posloupností. To znamená, že
Tvrzení \(a_n = \mathcal{O}(b_n)\) naopak říká, že \((a_n)_{n=1}^\infty\) neroste (v absolutní hodnotě) rychleji než \((b_n)_{n=1}^\infty\) pro velká \(n\). \(\mathcal{O}\) je tedy značně hrubší než \(\sim\).
Pro dvě posloupnosti \((a_n)_{n=1}^\infty\) a \((b_n)_{n=1}^\infty\) dokažte implikaci: pokud \(a_n \sim b_n\), potom \(a_n = \mathcal{O}(b_n)\).
Pokud nerovnost \(b_n > 0\) platí pro všechna \(n\in\mathbb{N}\) pak lze definici 10.15 přeformulovat do následujícího, často používaného, tvaru
V předchozí podkapitole jsme vypočetli limitu \begin{equation*} \lim_{n\to\infty} \frac{n^2}{2^n} = 0.\end{equation*} Posloupnost \((n^2 / 2^n)_{n=1}^\infty\) je tedy omezená. V notaci zavedené výše to znamená, že \begin{equation*} n^2 = \mathcal{O}(2^n).\end{equation*}
Demonstrujme dále výše zavedené pojmy a tvrzení na několika jednoduchých příkladech.
Platí \(50 \sin n = \mathcal{O}(1)\). Skutečně, stačí použít přímo definici \(\mathcal{O}\). Dokonce pro každé \(n\in\mathbb{N}\) platí \begin{equation*} |50 \sin n| \leq 50 \cdot 1.\end{equation*} Za konstantu v definici tedy lze vzít číslo \(50\).
Platí \(500 n = \mathcal{O}(n^2)\). Opět použijeme definici \(\mathcal{O}\), resp. alternativní formulaci (10.5). Pro každé \(n\in\mathbb{N}\) platí \begin{equation*} \frac{500n}{n^2} = \frac{500}{n} \leq 500.\end{equation*} Posloupnost \((500n/n^2)_{n=1}^\infty\) je tedy omezená, jak jsme chtěli dokázat.
Platí \begin{equation*} \frac{n^2 + n}{n^3 + n^2 + n + 1} \sim \frac{1}{n}.\end{equation*} Použijme tvrzení 3.31. Snadno vypočteme \begin{equation*} \begin{aligned} \lim_{n\to\infty} \frac{\frac{n^2 + n}{n^3 + n^2 + n + 1}}{\frac{1}{n}} &= \lim_{n\to\infty} \frac{n^3 + n^2}{n^3 + n^2 + n + 1} = \\ &= \lim_{n\to\infty} \frac{1 + \frac{1}{n}}{1 + \frac{1}{n} + \frac{1}{n^2} + \frac{1}{n^3}} = \frac{1+0}{1+0+0+0} = 1. \end{aligned}\end{equation*} A tvrzení tedy platí.
Necháváme čtenáři k ověření, že dále například platí \begin{equation*} \begin{aligned} n^2 + \frac{1}{2} n - 1 &\sim n^2, \\ 2 n &= \mathcal{O}(n^2\,), \\ n\sin n &= \mathcal{O}(n^2\,), \\ 4n^2 &= \mathcal{O}(n^2\,), \\ 10n &= \mathcal{O}(n), \\ n &= \mathcal{O}(10n). \end{aligned}\end{equation*}
Zápis \(a_n = \mathcal{O}(b_n)\) není příliš šťastný. Lepší je ho chápat ve smyslu \(a_n \in \mathcal{O}(b_n)\). Historicky se však ujal a používá se. Například pokud \(a_n = \mathcal{O}(n)\) a současně \(b_n = \mathcal{O}(n)\), neplyne odtud, že \(a_n = b_n\).
Všimněte si, že omezenost posloupnosti \((a_n)_{n=1}^\infty\) lze nyní snadno vyjádřit formulkou \(a_n = \mathcal{O}(1)\). Skutečně, dle definice existuje jistá konstanta \(c > 0\) a index \(n_0 \in \mathbb{N}\) splňující \(|a_n| \leq c\) pro každé \(n \geq n_0\). Odtud již snadno plyne omezenost posloupnosti \((a_n)_{n=1}^\infty\).