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 první, 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 7kilové cihličky. Za 3kilovou cihličku dostaneme 7 milionů Kč, za 4kilovou 10 milionů Kč a za 7kilovou 16 milionů Kč. Víme, že uneseme 185 kg zlata. Které cihličky máme vzít, abychom si z banky odnesli 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.