Search
Přednáška 1 v oddíle Přednášky
Vše to jsou množiny!
Užitečná pravidla:
Ř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))$?
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.
Pokud taková trojice funkcí nemůže existovat, zdůvodněte proč.
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.
Ř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}$?
$\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;
$\Theta(N)$, algoritmus hledá minimum v poli
Ú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.
Ú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 }
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 ; }
Ú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é zde.