Výpočet časové složitosti a asymptotické notace

  1. (Procvičení notací velké $\OO$, $\Omega$ a $\Theta$)
    Pro následující dvojice funkcí $f$ a $g$ rozhodněte, jestli platí $f=\OO(g)$ nebo $f=\Omega(g)$ a nebo oboje, tj. $f=\Theta(g)$.

    $n-100$ $n-200$
    $(n+42)^8$ $n^{8}$
    $n^{1/2}$ $n^{2/3}$
    $100n+\log n$ $n+(\log^2 n) $
    $n\log n $ $100 n \log (16n) $
    $\log 2n $ $\log 3n $
    $10\log n $ $\log (n^2) $
    $\log \log n $ $\sqrt{\log n} $
    $n^{1.01} $ $n\log n$
    $n^2/\log n$ $n \log^2 n$
    $n^{0.1}$ $\log^{10} n $
    $(\log n)^{\log n}$ $n/\log n$
    $\sqrt{n}$ $\log^5 n$
    $\sqrt{n}$ $n^{\sin n}$
    $n^{1/2}$ $2^{\log_2 n} $
    $n2^n$ $3^n $
    $2^n$ $2^{n+1} $
    $n!$ $2^n $
    $(\log n)^{\log n}$ $2^{(\log_2 n)^2} $
    $\sum_{i=1}^n i^k$ $n^{k+1} $
    $2^{\OO(n)}$ $5^{\OO(n)} $

    Pokud se chcete pocvičit ještě o něco více, tak seřaďte všechny výše uvedené funkce podle podle asymptotické časové složitosti (zápis “$=\OO$” bereme jako uspořádání “$\preceq$”).

  2. (Najděte chybu)
    Indukcí dokážeme, že $f(n)=n^2 \in \OO(n)$. Pro $n=1$ to platí. Předpokládejme tedy, že tvrzení platí až do nějakého $n$. Ukážeme, že platí i pro následníka. $f(n)= n^2 = (2n+1) + (n-1)^2 = \OO(n) + f(n-1) = \OO(n) + \OO(n) = \OO(n)$. Čtvrtá rovnost platí díky indukčnímu předpokladu $f(n-1)=O(n)$.
  3. (Procvičení výpočtu časové složitosti — násobení $a \cdot b$ pomocí sčítání)
    Dostaneme dvě čísla $a, b \in \NN$ a chceme spočítat jejich součin. Předpokládejme, že pracujeme na počítači, kde má každá proměnná neomezený počet bitů. Práce s takovými proměnnými není jednoduchá a tak nemůžeme použít instrukci pro násobení ani instrukci pro bitový posun. Máme k dispozici pouze instrukci pro sčítání. Pro jednoduchost předpokládejme, že součet dvou čísel trvá konstantní čas.1 

    1. Triviální řešení je následující:
      $mezivysledek:=b$
      for $i=2$   to $a$   do
      	$mezivysledek:= mezivysledek + b$
      return $mezivysledek$

      Ukažte, že tento algoritmu má exponenciální časovou složitost ve velikosti vstupu.

    2. Vymyslete řešení s lineární časovou složitostí ve velikosti vstupu.

Dolní odhad časové složitosti

  1. (Dolní odhad pro vyhledávání v setříděném poli na základě porovnávání)
    Pomocí binárního vyhledávání (půlení intervalu) umíme v čase $\OO(\log n)$ zjistit, jestli setříděné pole $\ARRAY{A}{1,\dots,n}$ obsahuje číslo $x$. Ukažte, že každý algoritmus, který pouze porovnává prvky pole s číselnou hodnotou, tj. ptá se na “$\ARRAY{A}{i}\leq z$?”, má časovou složitost v nejhorším případě alespoň $\Omega(\log n)$. Jinými slovy každému takovému algoritmu může ďábel podstrčit ošklivý vstup, na kterém algoritmus vykoná alespoň $\log n$ kroků.

Hledání algoritmu s co nejlepší časovou složitostí

  1. (Které číslo chybí?)
    Množina $C$ obsahuje všechna čísla $1$ až $n$ kromě jednoho. Na vstupu postupně dostanete všechna čísla z množiny $C$ a vaším úkolem je zjistit, které číslo v množině chybí. 

    1. Umíte to v lineárním čase?
    2. A co když můžeme použít jen konstantně mnoho paměti?
    3. Co když v množině budou chybět $2$ čísla? Jak rychle zjistíte, která to jsou?
  2. (Max gap)
    Dostanete $n$ reálných čísel z intervalu $\langle 0,1 \rangle$. První dvě z nich jsou vždy $0$ a $1$. Velikost mezery mezi čísly $a, b\in \RR$ je $|b-a|$. Mezera je prázdná, pokud interval mezi $a$ a $b$ neobsahuje žádné jiné ze zadaných čísel. Zjistěte, která dvě zadaná čísla mají mezi sebou největší prázdnou mezeru, a vypište je spolu s velikostí mezery.

    Umíte je najít v čase $\OO(n)$?

  3. (Palindrom)
    Palindrom je slovo které se čte stejně zepředu i pozpátku. Na vstupu dostanete řětězec $n$ znaků. Navrhněte algoritmus, který v řetězci co nejrychleji najde nejdelší palindrom a vypíše jeho délku. Své řešení otestujte například na řetězcích: “madam”, “mam”, “rotor”, “kuna nese nanuk”.

    Umíte to rozhodnout v čase $\OO(n)$?

Amortizovaná časová složitost

  1. (Nafukovací i smršťovací pole)
    V sekci o amortizované časové složitosti jsme si vysvětlili, jak funguje nafukovací pole. Co kdybychom chtěli přidat mazání prvků? Když už bude pole poloprázdné, tak bychom ho mohli smrštit na poloviční velikost. Rozmyslete si, při jaké obsazenosti pole by se mělo provádět nafukování nebo smršťování pole, aby amortizovaná časová složitost operací delete($x$) a insert($x$)byla stále konstantní.
  2. (Binární vyhledávání + přidávání prvků)
    Chceme si reprezentovat $n$-prvkovou množinu čísel $M$. Často budeme volat operace najdi($x$) a pridej($x$). Operace najdi($x$) zjistí, jestli $x\in M$. Operace pridej($x$) provede $M:= M\cup \{x\}$.

    K reprezentaci množiny $M$ použijeme následující datovou strukturu. Nechť $[n_{k-1}n_{k-2}\dots n_1 n_0]_2$ je binárním zápisem čísla $n$. Množinu $M$ si místo jednoho pole reprezentujeme pomocí $k:=\lceil\log (n+1) \rceil$ uspořádaných polí $A_0$, $A_1$, \dots, $A_{k-1}$ o velikostech $1$, $2$, $4$, \dots, $2^{k-1}$. Velikost pole $A_i$ je $2^i$. Každé pole $A_i$ je buď celé prázdné nebo celé plné, podle toho, jestli je $n_i=0$ nebo $n_i=1$. Celkový počet prvků ve všech polích je $\sum_{i=0}^{k-1} n_i 2^i = n$. Ačkoliv je každé pole setříděné, o velikostech prvků v různých polích nic nevíme.

    1. Popište, jak v této datové struktuře provádět operaci najdi($x$) a určete její časovou složitost v nejhorším případě.
    2. Popište, jak v této datové struktuře provádět operaci pridej($x$) a určete její časovou složitost v nejhorším případě. Kromě toho určete i její amortizovanou složitost.
    3. Zkuste vymyslet, jakým způsobem by se v datové struktuře dalo provádět mazání prvků.
  3. (Procvičení metody potenciálu: hledání následníka v binárním stromě)
    Máme binární vyhledávací strom $T$ a nějaký jeho vrchol $v$. Následník2 vrcholu $v$ je vrchol s nejmenším vyšším klíčem, než je hodnota klíče ve $v$. Nalezení následníka trvá v nejhorším případě čas $\OO(\mbox{hloubka $T$})$. Ukažte, že pokud budeme chtít najít $k$ následníků, tak to zvládneme v čase $\OO(k+\mbox{hloubka $T$})$.

    Nápověda: Nechť $w\in T$ je aktuální vrchol při hledání následníků. Zkuste potenciál $\Phi= (\mbox{hloubka $T$}- \mbox{hloubka $w$ v $T$}) + 2\cdot \#$pravých hran na cestě z kořene do $w$.