====== 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}}.