1. Asymptotická složitost

1 - Asymptotická složitost

Připomenutí teorie

Přednáška 1 v oddíle 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))$

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)} = a, a \in (0, \infty)$ , 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

Rozehřání

Řešená úloha 1: Který fragment programu z následujících dvou proběhne rychleji? (Předpokládáme, že oba běží v identickém SW/HW prostředí.)

int n = 100;
int sum = 0;
for (i = 0; i < n; i++)
  for (j = 0; j < i; j++)
    sum += i+j;

int n = 75;
int sum = 0;
for (i = 0; i < n; i++)
  for (j = 0; j < n; j++)
    sum += i+j;

Řešení

Ten nalevo, protože $\sum_{i=0}^{99} i = 100\frac{99}{2} = 4950 < 5625 = 75^2$

Vyplatí se znát vzorec pro součet $q$ členů aritmetické posloupnosti: $\sum_{i = 1}^{q} a_i = q \frac{a_1 + a_q}{2}$ . Vizuální důkaz.

Simulace běhu

Řešená úloha 2: Ke zpracování $k$ -tého řádku matice velikosti $n \times n$ je zapotřebí $2k$ operací. Kolik je potřeba operací ke zpracování celé matice?

a) $2n^2$
b) $n^2 / 2$
c) $n(n+1) / 2$
d) $n(n-1)$
e) $n(n+1)$

Řešení

Správně je e): Součet pro $n$ řádků (aritmetická posloupnost): $\sum_{k=1}^n 2k = n\frac{2 + 2n}{2} = n(n+1)$ .

⭐ Řešená úloha 3: Metoda A potřebuje k vyřešení úlohy $n^2 + 17$ operací, Metoda B potřebuje $2n + 80$ operací, přičemž celé číslo $n$ popisuje rozsah vstupních dat. Pro jaká $n$ je výhodnější použít metodu A?

Řešení

výpočet

Matematický pohled

Řešená úloha 4: Pro rostoucí spojité fukce $f$ , $g$ platí $f(x) \in \Omega(g(x))$ . Z toho plyne, že:

$f(x) \in \mathrm{O}(g(x))$
$f(x) \in \Theta(g(x))$
$g(x) \in \Theta(f(x))$
$g(x) \in \Omega(f(x))$
$g(x) \in \mathrm{O}(f(x))$

Řešení

e): $g(x) \in \mathrm{O}(f(x))$ ověříme snadno z definice.

Řešená úloha 5: 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í

Ano, například $f(x) = x$ a $g(x) = x + 1$ .

Řešená úloha 6: 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í

Může, například $f(x) = x^3, g(x) = x^2, h(x) = x$

Řešená úloha 7: 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í

$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$

Pokud si nejsme jistí, která ze dvou funkcí f(n) a g(n) má vyšší asymptotickou složitost, spočítáme limitu $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ pomocí L’Hospitalova pravidla.

Praktický pohled

Řešená úloha 8: 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í

$\Theta(n^2 \log_2(n))$ , algoritmus provede $n^2$ krát operaci která má složitost $\Theta(\log_2(n))$ .

Řešená úloha 9: 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í

$\Theta(N)$ , algoritmus hledá minimum v poli

Nevyřešitelné (zatím) úlohy

Motivační úloha 10: Plánujeme bankovní loupež a chceme si z trezoru banky odnést zlato v co největší hodnotě. Banka vede různé váhy zlatých cihliček. V trezoru mají 3, 4 a 7 kilové cihličky. Za 3 kilovou cihličku dostaneme 7 milionů Kč, za 4 kilovou cihličku dostaneme 10 milionů Kč a za 7 kilovou dostaneme 16 milionů Kč. Víme, že uneseme 185 kg zlata, které cihličky máme vzít, abychom si z banky odnesly cihličky v co největší hodnotě?

Motivační úloha 11: Sestavujeme nový nákladní vlak a máme k dispozici tři druhy nákladních vozů: Kontejnerový vůz, výsypný vůz a cisterna. Z bezpečnostích důvodů nesmí být dvě cisterny bezprostředně za sebou. Kolik různých vlaků s 10 vozy můžeme sestavit?

Motivační úloha 12: Připravujeme velkou databázi uživatelů a víme, že nejčastěji budeme vyhledávat podle sloupce "Příjmení". Chtěli bychom tedy indexovat tento sloupec. Jakou datovou strukturu bychom měli použít?

Další úlohy

⭐ Úloha 13: Stroj provádí $10^9$ operací za sekundu. Pro výpočet je k dispozici 1 hodina. Určete, jaká může být maximální hodnota $N_{\max}$ , která určuje velikost vstupních dat, v případě že počet nezbytných operací pro zpracování dat o velikosti $N$ je $N^{3/2}$ .

A co v případě že zpracování vyžaduje
a) $N^{5/4}$ operací
b) $N \cdot \log_2(N) \cdot \log_2 (\log_2 N)$ operací
c) $N^2 \cdot \log_2 N$ operací

Úloha 14: 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 15: Ukažte, že $\Theta(f(n) + g(n))$ a $\Theta(max(f(n), g(n)))$ jsou stejné množiny.

Úloha 16: Pro rostoucí spojité fukce $f$ , $g$ platí $f(x) \in \mathrm{O}(g(x))$ . Z toho plyne které z následujících tvrzení?

$f(x) \in \Theta(g(x))$
$f(x) \in \Omega(g(x))$
$g(x) \in \Theta(f(x))$
$g(x) \in \Omega(f(x))$
$g(x) \in \mathrm{O}(f(x))$

Úloha 17: 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 18: 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 19: 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 20: 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 21: 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 22: Je dána zafixovaná matice M o rozměru $N \times N$ . Máme postupně odpovídat na množství dotazů stejného formátu:

Jaký je součet všech hodnot v podmatici, která má levý horní roh na pozici $(i_1, j_1)$ a pravý dolní roh na pozici $(i_2, j_2)$ ?

Hodnoty $i_1, j_1, i_2, j_2$ budou v každém dotazu obecně jiné. K dispozici máte paměťový prostor stejně velký jako zabírá M. Určete, jaké hodnoty si musíte předpočítat, abyste na každý dotaz odpověděli v co nejkratším čase a nezávisle na velikosti hodnot $i_1, j_1, i_2, j_2$ .

implementace

⭐ Úloha 23: 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 24: 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 25: 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 26: 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 27: 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 28: Popište, jak vypočtete hodnotu $log_{10}(log_{10} N^{N!})$ pro $N = 10^7$ . 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.