Asymptotické složitosti

Pořádně formálně zpracované - takto řekl cvičící, že má vypadat vzorové řešení. Mé správné, ale jen pomocí slov téměř poslal do koše.

Ač to mistři v recodexu zapisovali $= O(n^2)$, tak se myslí $\in O(n^2)$, "Relace "=" znamená náležení do třídy funkcí."

Vycházíme z definice:

$$f(n) \in O(g(n)) \iff \exists c \in \reals^+ \ \exists n_0 \in \natnums \ \forall n \ge n_0: f(n) \le c \cdot g(n)$$

$$f, g \text{ jsou funkce } \natnums \rightarrow \reals^+$$

Cituji z Průvodce (2022, sekce 2.4 Asymptotická notace, str. 50):

Nechť $f, g: \natnums \rightarrow \reals$ jsou 2 funkce. Řekněme, že funkce $f(n)$ je třídy $O(g(n))$, jestliže existuje taková realná kladná konstanta $c$, že pro skoro všechna $n$ platí $f(n) \le c \cdot g(n)$. Skoro všemi $n$ se myslí, že nerovnost může selhat pro konečně mnoho výjímek, tedy, že existuje nějaké přirozené $n_0$ takové, že nerovnost platí pro všechna $n \ge n_0$. Funkci $g(n)$ se pak říká asymptotický horní odhad funkce f(n).

Na zápis $O(g)$ bychom se mohli dívat jako na množinu všech funkcí $f$, které splňují uvedenou definici. Proto můžeme místo "funkce $f$ je třídy $O(g)$" psát $f \in O(g)$. Navíc to umožní elegatně zapisovat různé vztahy typu $O(n) \subseteq O(n^2)$

Průvodce to definuje to pro $\reals$, ale tady v cvičení máme všechny funkce do $\reals^+$, a budeme toho v důkazech využívat, bude nám stačit definice pro $\reals^+$. Tu část s konstantně mnoho výjimkami budu používat.

$$f(n) \in \Omega(g(n)) \iff \exists c \in \reals^+ \ \exists n_0 \in \natnums \ \forall n \ge n_0: f(n) \ge c \cdot g(n)$$

$$f, g \text{ jsou funkce } \natnums \rightarrow \reals^+$$

Dokažte nebo vyvraťte tvrzení. Pro každou dvojici funkcí $f, g, f_1, f_2: N_0 \rightarrow \reals^+$ platí:

1. $n^2 + 6n + 4 = O(n^2)$

   $n^2 + 6n + 4 \in O(n^2)$

   $n^2 + 6n + 4 \le c \cdot n^2$

   $\frac{n^2 + 6n + 4}{n^2} \le c$

   $1 + \frac 6 n + \frac{4}{n^2} \le c$

   Platí např. pro $c = 10$, s tím, že $n_0 = 1$

2. $n^3 = O(n^2)$

   $n^3 \le c \cdot n^2$

   $\frac{n^3}{n^2} \le c$

   $n \le c$ neplatí, protože ať vybereme pro zvětšující se $n$ jakkoliv velké $c$, vždy bude existovat $n > c$ => nekonečný počet výjimek => vyvráceno

3. Pokud $f(n) = O(g(n))$, pak $2^{f(n)} = O(2^{g(n)})$

   $f(n) \in O(g(n)) \implies 2^{f(n)} \in O(2^{g(n)})$

   Dosaďme tam např. $f(n) = 2n$, a $g(n) = n$. Levá strana platí:

   $2n \le c \cdot n$

   $2 \le c$, platí

   Pravá strana neplatí:

   $2^{2n} \le c_2 \cdot 2^n$

   $\frac{2^{2n}}{2^n} \le c_2$

   $2^n \le c_2$ neplatí, protože ať už pro rostoucí $2^n$ vybereme jakékoli $c_2$, vždy bude existovat $2^n > c_2$ => nekonečný počet výjimek => neplatí

   Když neplatí pravá strana implikace, implikace neplatí.

4. $f(n) = O(f(n)^2)$

   $f(n) \in O(f(n)^2)$

   Tohle je chyták!!! Přestože se v informatice u složitosti běžně nesetkáváme s klesajícími funkcemi, může $f(n)$ zde být klesající (protože $f$ je pouze nějaké $f: N_0 \rightarrow \reals^+$, nevíme o něm nic víc), a pak tvrzení platit nebude.

   Například předpokládejme, že $f(n) = \frac 1 n$:

   $\frac 1 n \le c \cdot \frac{1}{n^2}$

   $n \le c$ => spor, viz úloha 2., vždy lze nalézt $n > c$

   Tvrzení neplatí.

5. Nechť $f(n) = f_1(n) + f_2(n)$ a $f_1(n) = O(f_2(n))$. Pak $f(n) = O(f_2(n))$

   $f(n) = f_1(n) + f_2(n) \land f_1(n) \in O(f_2(n)) \implies f(n) \in O(f_2(n))$

   pro $n > n_0$:

   $f_1(n) \in O(f_2(n))$

   $f_1(n) \le c_1 \cdot f_2(n)$

   Teď jelikož $f(n) = f_1(n) + f_2(n)$, tak přičteme k oběma stranám $f_2(n)$:

   $f_1(n) + f_2(n) \le c_1 \cdot f_2(n) + f_2(n)$

   $f_1(n) + f_2(n) \le (c_1 + 1) \cdot f_2(n)$

   $f_1(n) + f_2(n) \le c \cdot f_2(n)$

   $f(n) \le c \cdot f_2(n)$

   $f(n) \in O(f_2(n))$

   Platí.

6. Nechť $f_1$ a $f_2$ jsou funkce, pro které platí $f_1(n) = O(g(n))$ a $f_2(n) = O(g(n))$. Potom $f_1(n) + f_2(n) = O(g(n))$

   $f_1(n) \in O(g(n)) \land f_2(n) \in O(g(n)) \implies f_1(n) + f_2(n) \in O(g(n))$

   pro $n > n_{0_1}$ platí: $f_1(n) \le c_1 \cdot g(n)$

   pro $n > n_{0_2}$ platí: $f_2(n) \le c_2 \cdot g(n)$

   Všimněme si, že platnost těchto 2 nerovnic začíná od různých konstant. Když tedy budeme chtít něco trvdit pro obě zároveň, tedy například v $f_1(n) + f_2(n) \le g(n)$, tak bychom měli provést průnik intervalů $[n_{0_1}, \infty)$ a $[n_{0_2}, \infty)$. Tedy zvolit maximum z těch dvou.

   $n_0$ je $\ge$ $\max\{n_{0_1}, n_{0_2}\}$, abychom tedy splnili podmínku o konečném množství výjimek.

   pro $n_0 \ge \max\{n_{0_1}, n_{0_2}\}$:

   $f_1(n) + f_2(n) \le c \cdot g(n)$

   $c_1 \cdot g(n) + c_2 \cdot g(n) \le c \cdot g(n)$

   $c_1 + c_2 \le c$ => vždy najdeme konstantu větší než součet 2 jiných

7. Nechť $f_1$ a $f_2$ jsou funkce, pro které platí $f_1(n) = O(g_1(n))$ a $f_2(n) = O(g_2(n))$. Potom $f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$

   $f_1(n) \in O(g_1(n)) \land f_2(n) \in O(g_2(n)) \implies f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$

   pro $n \ge n_1$: $f_1(n) \le c_1 \cdot g_1(n)$

   pro $n \ge n_2$: $f_2(n) \le c_2 \cdot g_2(n)$

   Pokud na levé straně implikace má platit obojí současně, tak pro $n \ge \max\{n_1, n_2\}$.

   Pravá strana pak též pro $n \ge \max\{n_1, n_2\}$:

   $f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$

   $f_1(n) \cdot f_2(n) \le g_1(n) \cdot g_2(n)$

   Dosadíme levou stranu (násobit, dělit beze změny znaménka nerovnosti můžeme protože z definice $c, g_1, g_2$ víme, že se jedná o kladná čísla (kladná konstanta a zobrazení do $\reals^+$)):

   $(c_1 \cdot g_1(n)) \cdot (c_2 \cdot g_2(n)) \le g_1(n) \cdot g_2(n)$

   $c_1 \cdot c_2 \le c$ => platí, vždy lze najít konstantu, která je $\ge$ součinu 2 čísel.

   Lze postupovat i 2. způsobem: nerovnice $f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$ a $f_1(n) \cdot f_2(n) \le g_1(n) \cdot g_2(n)$ spolu vynásobíme (můžeme protože z definice $c, g_1, g_2$ víme, že se jedná o kladná čísla):

   $f_1(n) \cdot f_2(n) \le c_1 \cdot g_1(n) \cdot c_2 \cdot g_2(n)$

   $f_1(n) \cdot f_2(n) \le \underbrace{(c_1 \cdot c_2)}_{c\text{ v cílené rovnici}} \cdot g_1(n) \cdot g_2(n)$

   $c_1 \cdot c_2$ je člen $c$ v cílené rovnici (té, kam se snažíme v důkazu dojít), tedy $\exists c = c_1 \cdot c_2$, aby nerovnosti a tedy i tvrzení platily.

8. $f = O(g)$ potom $g = \Omega(f)$

   $$f(n) \in \Omega(g(n)) \iff \exists c \in \reals^+ \ \exists n_0 \in \natnums \ \forall n \ge n_0: f(n) \ge c \cdot g(n)$$

   Tedy stejná definice jako pro $O(g(n))$, ale otočené znaménko nerovnosti.

   pro $n > n_0$:

   $f(n) \in O(g(n)) \implies g(n) \in \Omega(f(n))$

   levá strana:

   $f(n) \in O(g(n))$

   $f(n) \le c_1 \cdot g(n)$

   $f(n) \cdot \frac{1}{c_1} \le g(n)$

   $g(n) \ge f(n) \cdot \frac{1}{c_1}$

   pravá strana:

   $g(n) \in \Omega(f(n))$

   $g(n) \ge c \cdot f(n)$

   Takže máme:

   $g(n) \ge \frac{1}{c_1} \cdot f(n) \implies g(n) \ge c \cdot f(n)$

   A to už platí, protože je to vlastně stejná nerovnost. Vždy lzde stanovit $c_1$ resp. $c_2$ tak aby platilo $\frac{1}{c_1} = c_2$ a platí pro stejná $n$ jako $f(n) \in O(g(n))$.

Ještě pár příkladů, tentokrát z Průvodce (2.4 Asymptotická notace, str. 51). Ty už ovšem nikým oveřené nejsou.

Ještě definice:

Řekněme, že funkce $f(n)$ je třídy $\Theta(g(n))$, jestliže $f(n)$ je jak třídy $O(g(n))$, tak třídy $\Omega(g(n))$.

Symboly $\Omega$ a $\Theta$ opět mohou značit i příslušné množiny funkcí. Pak jistě platí $\Theta(g) = O(g) \cap \Omega(g)$

1. Nalezněte co nejvíc asymptotických vztahů mezi těmito funkcemi $n$, $\log n$, $\log \log n$, $\sqrt{n}$, $n^{\log n}$, $2^n$, $n^{3/2}$, $n!$, $n^n$.

   (jelikož jsme v informatice, tak ty logaritmy uvažujeme o základu 2, ale to je jedno - logaritmus o základu 10 se liší konstanta krát)

   Třeba $\log(n) \in O(n)$. Mohli bychom se podívat na grafy $y = \log_2(x)$ a $y = n$, a říct, že to je zcela zřejmé, ale pokud bychom to chtěli formálně, a neumíme nic z analýzy, tak to můžeme udělat indukcí.

   $\log_2(n) \in O(n)$

   $\log_2(n) \le c \cdot n$

   Konstanta $c$ existuje, př. to můžeme ukázat pro $c = 1$. A $n_0 = 1$.

   $n = 1$: $\log_2(1) \le 1$ = $0 \le 1$, platí

   Chceme ukázat, že z $n = k$: $\log_2(k) \le k$ plyne $n = k+1$: $\log_2(k+1) \le k + 1$.

   Logaritmus je funkce rostoucí, tudíž můžeme říct, že:

   $\log_2(k+1) \le \log_2(2k)$, protože $2k > k + 1$ pro $k \ge 1$

   $\log_2(2k) = \log_2(k) + \log_2(2) = \log_2(k) + 1$

   $\log_2(k+1) \le \log_2(k) + 1$

   A teď využijeme indukčního předpokladu, dosadíme za $\log_2(k)$ výraz, který je větší nebo roven:

   $\log_2(k+1) \le k + 1$

   To je to, k čemu jsme se chtěli dostat.

4. Dokažte, že $n \log n \notin O(n)$:

$n \log n \in O(n)$

$n \log n \le c \cdot n$

$\log n \le c$ => neplatí, my jsme však chtěli $n \log n \notin O(n)$, tak to platí:

Tedy:

$n \log n \notin O(n)$

$n \log n > c \cdot n$

$\log n > c$ => platí