Při určování asymptotické časové složitosti nás zajímá chování algoritmů na hodně velkých datech. Vezměte si papír, hodně velký papír, a nakreslete na něj grafy všech funkcí představujících časovou složitost, které vás napadnou. Při pohledu zblízka uvidíme velký rozdíl mezi funkcemi $\log n$, $n$, $2^n$, ale i mezi $n$, $5n$ a $50n$. Asymptotická časová složitost se na tento papír dívá z velké dálky, třeba až z Marsu (musíme mít hodně velký papír). Při jejím pohledu všechny funkce, které se liší jen multiplikativní konstantou, “splynou” v jednu “rozmazanou funkci”. Z takové dálky zůstane vidět jen propastný rozdíl mezi funkcemi $\log n$, $n$, $2^n$ (viz tabulka na straně \pageref{tabulka_rustu_funkci} zachycující, jak rychle rostou některé funkce).

Chceme zavést značení, které bude říkat, že funkce lišící se pouze multiplikativní konstantou, patří do stejné třídy.

Definice: Nechť $f$ a $g$ jsou dvě funkce z přirozených čísel do přirozených čísel. Řekneme, že

  • $f(n) = \OO(g(n))$ — (čte se “$f$ je velké O od funkce $g$”) právě tehdy, když existuje konstanta $c>0$ a $n_0$ takové, že pro každé $n\geq n_0$ platí $f(n)\leq c \cdot g(n)$.
  • $f(n) = \Omega(g(n))$ — (čte se “$f$ je omega od funkce $g$”) právě tehdy, když existuje konstanta $c>0$ a $n_0$ takové, že pro každé $n\geq n_0$ platí $f(n)\geq c \cdot g(n)$.
  • $f(n) = \Theta(g(n))$ — (čte se “$f$ je theta od funkce $g$”) právě tehdy, když zároveň $f(n) = \OO(g(n))$ i $f(n) = \Omega(g(n))$.

Slovy se dá asymptotická notace $f(n) = \OO(g(n))$ popsat jako $f$ neroste řádově rychleji než funkce $g$. Zápis $f(n) = \Omega(g(n))$ znamená, že funkce $f$ roste řádově aspoň tak rychle jako funkce $g$ a zápis $f(n) = \Theta(g(n))$, že obě funkce rostou řádově stejně rychle.

Můžeme si to vysvětlit i na obrázku vpravo. Notace $f(n) = \OO(g(n))$ říká, že existuje taková konstanta $c$, že od určitého $n_0$ už leží graf funkce $f(n)$ pod grafem funkce $c\cdot g(n)$ (v šedě vyznačené oblasti).

Uveďme ještě pár příkladů. Platí $2^{56} = \OO(1)$, $30n = \OO(n)$, $n = \OO(n^2)$, $n^{30} = \OO(2^n)$, ale také $5n^2 + 30n = \OO(n^2)$, protože $5n^2 + 30n \leq 35 n^2 = \OO(n^2)$.

Pozor na značení! Přesněji bychom měli psát $f \in \OO(g)$ a říkat “$f$ je třídy $\OO(g)$” a nebo “$f$ patří do třídy $\OO(g)$”. Značení s “$=$” může být zavádějící, protože $\OO(x) = \OO(x^2)$, ale $\OO(x^2) \not= \OO(x)$. Musíme ho chápat spíše jako “$=\OO$” ve významu “$\preceq$”. Proto se také $f=\OO(g)$ někdy čte jako “$f$ je asymtoticky menší nebo rovno $g$”.

Lemma: Nechť $f_1$, $f_2$, $g_1$, $g_2$ jsou funkce takové, že $f_1\in \OO(g_1)$, $f_2\in \OO(g_2)$, $k$ je konstanta a $h$ je rostoucí funkce. Potom

  • $f_1\cdot f_2 \in \OO(g_1 \cdot g_2)$
  • $f_1+f_2 \in \OO(g_1+g_2) = \OO(\max(g_1, g_2))$
  • $k \cdot f_1 \in \OO(g_1)$
  • $f_1(h(n)) \in \OO(g_1(h(n)))$, ale také $h(f_1(n)) \in \OO(h(g_1(n)))$.

Mezi často používané odhady patří následující. Pro každé $a\leq b$ platí $n^a=\OO(n^b)$. Pro každé $k$ platí $n^k =\OO(2^n)$. To je ekvivalentní s $\log^k n = \OO(n)$. Zkuste si tyto odhady i předchozí lemma dokázat (je to jen cvičení s funkcemi, limitami a použití definice velkého $\OO$).

Definice vhodná pro výpočty: Asymptotickou notaci můžeme definovat i přes limitu. $$f(n)=\OO(g(n)) \;\Longleftrightarrow\; \lim_{n\to \infty} \frac{f(n)}{g(n)} \in \langle 0,+\infty)$$ $$f(n)=\Omega(g(n)) \;\Longleftrightarrow\; \lim_{n\to \infty} \frac{f(n)}{g(n)} \in (0,+\infty \rangle$$ Tato metoda je lepší pro počítání, ale musíme být trochu zběhlí v počítání limit. Zkuste si dokázat, že definice přes limitu implikuje námi uvedenou definici. Je to jednoduché cvičení na definici limity.

Příklad: Potřebujeme zjistit, jestli platí $2n^2 + 4n -5 =\OO(n^2)$. Podíváme se tedy na $\lim_{n\to \infty} \frac{2n^2 + 4n -5}{n^2} = 2$. Když si zvolíme $\varepsilon>0$, například $\varepsilon = 3$, tak z definice limity dostaneme, že existuje $n_0$ takové, že pro každé $n\geq n_0$ platí $\frac{2n^2 + 4n -5}{n^2} < 2+\varepsilon = 5$. Po přenásobení nerovnosti faktorem $n^2$ je to přesně definice vztahu $2n^2 + 4n -5 =\OO(n^2)$.