====== 1 - Asymptotická složitost ====== /* Toto cvičení prochází úpravou, zatím využijte následující zdroje. {{:courses:a4b33alg:cviceni02upd.pdf|pdf}} {{:courses:a4b33alg:cviceni1resene.pdf|pdf}} {{:courses:a4b33alg:a4b33alg_s01_solutions.pdf| řešené příklady}} */ ==== Shrnutí teorie ==== Přednáška 1 v oddíle [[courses:b4b33alg:prednasky|Přednášky]] * Horní ("Big-O", Omikron): $f(n) \in \mathrm{O}(g(n)) \Leftrightarrow \exists c > 0, \exists n_0, \forall n > n_0: f(n) \leq c \cdot g(n)$ * Dolní (Omega): $f(n) \in \Omega(g(n)) \Leftrightarrow \exists c > 0, \exists n_0, \forall n > n_0: f(n) \geq c \cdot g(n)$ * Optimální (Theta): $f(n) \in \Theta(g(n)) \Leftrightarrow f(n) \in \mathrm{O}(g(n)) \land f(n) \in \Omega(g(n)) $ {{ :courses:b4b33alg:internal:cviceni:asymp_sets.png?400|}} Vše to jsou množiny! Užitečná pravidla: * $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, pak $f(n) \in \mathrm{O}(g(n))$, ale $f(n) \notin \Theta(g(n))$ * $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$, pak $f(n) \in \Omega(g(n))$, ale $f(n) \notin \Theta(g(n))$ * $\lim_{n \to \infty} \frac{f(n)}{g(n)} =$ konst., pak $f(n) \in \Theta(g(n))$ * Na základu logaritmu nezáleží * Při součtu 2 funkcí stačí ta která je asymptoticky rychleji rostoucí, neboli $\Theta(f(n) + g(n)) = \Theta(max(f(n), g(n)))$. ==== Řešené úlohy ==== === Matematický pohled === **Řešená úloha 1:** Pro rostoucí spojité fukce $f$, $g$ platí $f(x) \in \Omega(g(x))$. Z toho plyne, že a) $f(x) \in \mathrm{O}(g(x))$ // b) $f(x) \in \Theta(g(x))$ // c) $g(x) \in \Theta(f(x))$ // d) $g(x) \in \Omega(f(x))$ // e) $g(x) \in \mathrm{O}(f(x))$ ++++ Řešení (rozbalit)| **e)**: $g(x) \in \mathrm{O}(f(x))$ ověříme snadno z definice. ++++ ----- **Řešená úloha 2:** Pro dvě spojité funkce $f$, $g$ rostoucí na celém $\mathbb{R}$ platí $f(x) < g(x)$ pro každé $x \in \mathbb{R}$. Je možné, že $f(x) \in \Omega(g(x))$? ++++ Řešení (rozbalit)| Ano, například $f(x) = x$ a $g(x) = x + 1$. ++++ ---- **Řešená úloha 3:** Uveďte příklad tří rostoucích funkcí reálné proměnné $f(x)$, $g(x)$ a $h(x)$, pro které současně platí všechny tři následující vztahy. * $f(x) \notin \mathrm{O}(g(x))$ * $g(x) \notin \Theta(h(x))$ * $h(x) \notin \Omega(f(x))$ Pokud taková trojice funkcí nemůže existovat, zdůvodněte proč. ++++ Řešení (rozbalit)| Může, například $f(x) = n^3, g(x) = n^2, h(x) = n$ ++++ ---- **Řešená úloha 4:** Seřaďte následující funkce dle asymptotické složistosti, identifikujte asymptoticky ekvivalentní funkce. |$n \log_2 n$|$5n$|$n^n$|$\log_2 n$| |$2^n$|$\sqrt[3]{n^2}$|$n^{1000}$|$\ln n$| |$1$|$n \log_2 n + 7n$|$3^n$|$n!$| |$n$|$\log_4 n$|$2^{\log_2 n}$|$3^n + 2^n$| ++++ Řešení (rozbalit)| - $1$ - $\log_4 n, \log_2 n, \ln n$ - $\sqrt[3]{n^2}$ - $n, 5n, 2^{\log_2 n}$ - $n \log_2 n, n \log_2 n + 7n$ - $n^{1000}$ - $2^n$ - $3^n, 3^n + 2^n$ - $n!$ - $n^n$ ++++ ---- === Praktický pohled === **Řešená úloha 5:** Algoritmus $\mathcal{A}$ prochází matici o velikosti $n \times n$ a s každým prvkem provádí akci, jejíž složitost je $\Theta(\log_2(n))$. Jaká je celková (optimální) asymptotická složitost algoritmu $\mathcal{A}$? ++++ Řešení (rozbalit)| $\Theta(n^2 \log_2(n))$, algoritmus provede $n^2$ krát operaci která má složitost $\Theta(\log_2(n))$. ++++ ---- **Řešená úloha 6:** Jaká je asymptotická složitost následujícího algoritmu? // array has size N and contains positive integers if (array.length == 0) return −1; int val = array[0]; for (int i = 1; i < N ; i++) if (array[i] < val) val = array[i]; return val; Co je výstupem algoritmu? ++++ Řešení (rozbalit)| $\Theta(N)$, algoritmus hledá minimum v poli ++++ ---- ==== Další úlohy ==== **Úloha 7:** Ukažte, že $\Theta(\log_a n)$ a $\Theta(\log_b n)$ jsou stejné množiny. (Za předpokladu, že $a$ i $b$ jsou kladná čísla) ---- **Úloha 8:** Ukažte, že $\Theta(f(n) + g(n))$ a $\Theta(max(f(n), g(n)))$ jsou stejné množiny. ---- **Úloha 9:** Pro rostoucí spojité fukce $f$, $g$ platí $f(x) \in \mathrm{O}(g(x))$. Z toho plyne které z následujících tvrzení? a) $f(x) \in \Theta(g(x))$ \\ b) $f(x) \in \Omega(g(x))$ \\ c) $g(x) \in \Theta(f(x))$ \\ d) $g(x) \in \Omega(f(x))$ \\ e) $g(x) \in \mathrm{O}(f(x))$ ---- **Úloha 10:** Pro dvě spojité funkce $f$, $g$ rostoucí na celém $\mathbb{R}$ platí $f(x) \notin \Omega(g(x))$, $f(x) \notin \Theta(g(x))$. Jsou následující tvrzení pravdivé? a) $g(x) \in \mathrm{O}(f(x))$ \\ b) $g(x) \in \Theta(f(x))$ \\ c) $f(x) < g(x)$ pro každé $x \in \mathbb{R}$ \\ d) $f(x) \leq g(x)$ pro každé $x \in \mathbb{R}$ \\ e) může existovat $y \in \mathbb{R}$ takové, že $f(y) > g(y)$ ---- **Úloha 11:** Který z následujících výroků je nepravdivý? a) $x\log_2(x) \in \mathrm{O}(x^2 - x)$ \\ b) $x\log_2(x) \in \mathrm{O}(x^2 - \log_2(x))$ \\ c) $x\log_2(x) \in \Omega(x^2 - \log_2(x))$ \\ d) $x\log_2(x) \in \Omega(x + \log_2(x))$ \\ e) $x\log_2(x) \in \Theta(x \log_2(x^2))$ ---- **Úloha 12:** Uveďte příklad tří rostoucích funkcí reálné proměnné $f(x)$, $g(x)$ a $h(x)$, pro které současně platí všechny tři následující vztahy. * $f(x) \notin \mathrm{O}(g(x))$ * $g(x) \notin \Omega(h(x))$ * $h(x) \notin \Theta(f(x))$ Pokud taková trojice funkcí nemůže existovat, zdůvodněte proč. ---- **Úloha 13:** Algoritmus $\mathcal{A}$ prochází pole s $n$ prvky. Při zpracování prvku na pozici $k$ provede $k+n$ operací. Jaká je asymptotická složitost algoritmu $\mathcal{A}$? ---- **Úloha 14:** Matice A má $M$ řádků a $N$ sloupců indexovaných od $0$. Na zpracování prvku matice na pozici $[r][s]$, ($0 \le r < M, 0 \le s < N$) je zapotřebí právě $s + r$ operací, z nichž každá má konstantní složitost. Jaká je asymptotická složitost zpracování celé matice? ---- **Úloha 15:** Jaká je asymptotická složitost následujícího algoritmu v závislosti na N? int [] a = new int [N]; for (i = 0; i < N; i++) a[i] = N; for (i = 0; i < N; i++) while (a[i] > 0) { print (a[i]); a[i] = a[i] / 2 ; // integer division } Co v případě, že pole nenaplníme $N$ ale $i$, neboli řádek 3 bude vypadat ''a[i] = i;''? ---- **Úloha 16:** Jaká je asymptotická složitost následujícího algoritmu v závislosti na N? int [] a = new int [N]; for (i = 0; i < N; i++) a[i] = 1; for (i = 1; i < N; i++) while (a[i] <= 2*a[i-1]) { print (a[i]); a[i] = a[i] + 1; } ---- **Úloha 17:** Jaká je asymptotická složitost následujícího algoritmu? for (int i = 0; i < N − 1 ; i++) for (int j = 0; j < N − i − 1 ; j++) if (array[j] < array[j + 1]) { int tmp = array[j] ; array[j] = array[j + 1] ; array[j+1] = tmp ; } Co provádí tento algoritmus? ---- **Úloha 18:** Na obvodu kružnice jsou v libovolně nepravidelných intervalech vyznačeny body očíslované po řadě za sebou 1, 2, ..., N. Máme určit počet všech takových trojúhelníků, jejichž vrcholy leží v očíslovaných bodech a které neobsahují střed kružnice jako svůj vnitřní bod. Navrhněte algoritmus a určete jeho asymptotickou složitost. (Řešte analogickou úlohu pro konvexní čtyřúhelníky.) ---- **Úloha 19:** Na výstup máme vypsat všechna kladná celá čísla, která jsou menší než dané číslo N a která ve svém binárním zápisu obsahují právě 3 jedničky. Jaký bude asymptotická složitost efektivního algoritmu? Algoritmus lineární vůči N je neefektivní. ---- **Úloha 20:** Popište, jak vypočtete hodnotu $log_{10}(log_{10} N^{N!})$ pro $N = 107$. Nepoužívejte aproximace jako např. Stirlingův vzorec apod. Jak dlouho bude trvat výpočet na Vašem osobním počítači? ---- Řešení k posledním 3 úlohám je popsané {{:courses:a4b33alg:a4b33alg_s01_solutions.pdf | zde}}.