Cvičenie - Polynomiálne algoritmy a \(O(f(n))\).

Ciele

Zvládnuť základné definície.
Rozlíšiť verzie optimalizačných problémov.
Určiť výpočtovú zložitosť pomocou funkcie \(O(f(n))\).

Postup

Príklad: Aká je výpočtová zložitosť jednotlivých krokov a celková výpočtová zložitosť popísaného algoritmu na výpočet súčinu dvoch štvorcových \(n\times n\) matíc \(A=(a_{ij}), B=(b_{ij})\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij}), \, B=(b_{ij})\) sú \(n\times n\) matice. Potom pre ich súčinovú maticu \(C=(c_{ij})\) platí: \[c_{ij}=\sum\limits_{k=1}^n a_{ik}\times b_{kj}.\]

Počet operácií \(+\) pre výpočet jedného elementu \(c_{ij}\) je \(n-1\). Výpočtová zložitosť je \(O(n)\).

Počet operácií \(\times \) pre výpočet jedného elementu \(c_{ij}\) je \(n\). Výpočtová zložitosť je \(O(n)\).

Celkový počet operácií pre výpočet jedného elementu \(c_{ij}\) je \(n-1+n=2n-1\). Výpočtová zložitosť je \(O(n)\).

Celkový počet operácií pre výpočet všetkých elementov matice \(C\) je \(n^2(2n-1)\). Celková výpočtová zložitosť popísaného algoritmu je preto \(O(n^3)\).
Zobraziť riešenie Skryť riešenie
Príklad: Aká je výpočtová zložitosť jednotlivých krokov a celková výpočtová zložitosť popísaného algoritmu na výpočet mocniny \(A^p\) štvorcovej \(n\times n\) matice \(A=(a_{ij})\) pre \(p\in N\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Potom pre jej \(p-\)tú mocninu \(A^p=(a^{(p)}_{ij})\) platí: \[a^{(p)}_{ij}=\sum\limits_{k=1}^n a^{(p-1)}_{ik}\,a_{kj}.\] Vytvoríme postupnosť \(A,\,A^2,\,\ldots \,,\,A^{p}\).

Podľa predchádzajúceho príkladu počet operácií potrebných na výpočet súčinu dvoch štvorcových \(n\times n\) matíc je \(n^2(2n-1)\). Výpočtová zložitosť je \(O(n^3)\).

Počet násobení matíc je \(p-1\). Celkový počet operácií pre výpočet matice \(A^p\) je teda \((p-1)n^2(2n-1)\). Celková výpočtová zložitosť popísaného algoritmu je \(O(pn^3)\).
Zobraziť riešenie Skryť riešenie
Príklad: Aká je výpočtová zložitosť jednotlivých krokov a celková výpočtová zložitosť popísaného algoritmu na výpočet metrickej matice \[\Gamma(A)=A\oplus A^2\oplus\dots\oplus A^n,\] kde \(A=(a_{ij})\) je \(n\times n\) matica a operácia \(\oplus\) reprezentuje maximum a operácia \(\otimes\) reprezentuje \(+\)?
Riešenie:

Predpokladajme, že \(A=(a_{ij})\) je \(n\times n\) matica. Podľa predchádzajúceho príkladu je počet operácií potrebných na vytvorenie postupnosti za sebou idúcich mocnín zadanej matice \(A,\,A^2,\,\ldots \,,\,A^{n}\) daný hodnotou \((n-1)n^2(2n-1)\). Výpočtová zložitosť tohto kroku je \(O(n^4)\).

Počet operácií \(\oplus\) pre výpočet jedného prvku metrickej matice \(\gamma_{ij}\) je daný hodnotou \(n-1\). Výpočtová zložitosť je \(O(n)\).

Celkový počet operácií \(\oplus\) potrebných na výpočet všetkých prvkov metrickej matice je \(n^2(n-1)\). Výpočtová zložitosť kroku je \(O(n^3)\).

Celkový počet operácií na výpočet metrickej matice \(\Gamma(A)\) je \((n-1)n^2(2n-1)+n^2(n-1)\). Celková výpočtová zložitosť popísaného algoritmu je \(O(n^4)\).
Zobraziť riešenie Skryť riešenie
Príklad: Dokážte, že platí, resp. nájdite kontrapríklad, že neplatí rovnosť \[(\ln n)^k=O(n^\epsilon)\] pre všetky \(k\in N\) a pre všetky \(\varepsilon>0.\) Použite: \(g(n)=O(f(n))\) vtedy a len vtedy, ak existuje \(c>0\), že platí \(g(n)\leq c\cdot f(n)\).
Riešenie:

Vypočítame limitu \[\lim\limits_{n\rightarrow \infty}\frac{\left(\ln n\right)^k}{n^\varepsilon}= \left(\lim\limits_{n\rightarrow \infty}\frac{\ln n}{n^{\frac{\varepsilon}{k}}}\right)^k= \left(\lim\limits_{n\rightarrow \infty}\frac{\frac{1}{n}}{\frac{\varepsilon}{k}n^{\frac{\varepsilon}{k}-1}}\right)^k= \left(\frac{k}{\varepsilon}\lim\limits_{n\rightarrow \infty}\frac{1}{n^{\frac{\varepsilon}{k}}}\right)^k=0\]

Stačí položiť \(c=1\) a tvrdenie platí pre všetky \(k\in N\) a pre všetky \(\varepsilon>0.\)
Zobraziť riešenie Skryť riešenie
Príklad: Aká je veľkosť vstupu pre grafové problémy.
Riešenie:

Predpokladajme, že graf \(G=(V,E)\) je reprezentovaný maticou susednosti \(A=(a_{ij})\), kde \(a_{ij}=1\), ak \((v_i,v_j)\in E\) a \(a_{ij}=0\), inak.

Potom veľkosťou vstupu môže byť množina \(|E|=n^2\), ale často sa z dôvodu riedkych matíc pri charakterizácii grafových algoritmov používa dvojica \(|V|=n, |E|=n^2\).

Celkový počet operácií potrebných na výpočet objektu grafového problému je možné vyjadriť ako násobok hodnôt \( O(|V|)\) alebo \(O(|E|)\).
Zobraziť riešenie Skryť riešenie
Príklad: Nech \(f:N\rightarrow N\) a \(g:N\rightarrow N\) sú funkcie definované nasledovne \[f(n)=\left\{ \begin{array}{l} n^2\text{ ak } n \text{ je prvočíslo,} \\ n^3\text{ inak,} \end{array}\right. \quad \quad g(n)=\left\{ \begin{array}{l} n^2\quad \text{ ak } n \text{ je nepárne,} \\ n^3\quad \text{ inak.} \end{array}\right. \] Analyzujte, ktoré z rovností sú, kedy pravdivé: \[f(n)=O(g(n)),\ \text{resp. }\ g(n)=O(f(n)).\]
Riešenie: Môžu nastať nasledujúce prípady:

Predpokladajme, že \(n\) je nepárne číslo a \(n\) nie je prvočíslo. Potom \(f(n)=n^3\) a \(g(n)=n^2\). Pre \(c=1\) platí \(g(n)=O(f(n)).\) Naviac, neexistuje \(c> 0\), ktoré nie je funkciou \(n\) a také, že \(n^3=O(n^2)\).

Predpokladajme, že \(n\) je nepárne číslo a \(n\) je prvočíslo. Potom \(f(n)=n^2\) a \(g(n)=n^2\). Pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)

Predpokladajme, že \(n\) je párne číslo a \(n\) je prvočíslo. Jediné číslo splňajúce podmienku prepokladu je \(n=2\). V tomto prípade pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)

Predpokladajme, že \(n\) je párne číslo a \(n\) nie je prvočíslo. Potom \(f(n)=n^3\) a \(g(n)=n^3\). Pre \(c=1\) platí \(f(n)=O(g(n))\) a aj \(g(n)=O(f(n)).\)
Zobraziť riešenie Skryť riešenie
Príklad: Analyzujte počet operácií Floydov-Warshallovho algoritmu.
Riešenie: Floydov-Warshallov algoritmus

Vstup: \(n\times n\) matica \((c_{ij})\) s nezápornými vstupmi

Výstup: \(n\times n\) matica \((d_{ij})\), kde \(d_{ij}\) je najkratšia vzdialenosť z vrchola \(i\) do vrchola \(j\).

begin

for all \(i\neq j\) do \(d_{ij}:=c_{ij}\);

for\(i=1,2,\dots,n\) do \(d_{ii}:=\infty\);

for\(j=1,2,\dots,n\) do

for \(i=1,2,\dots,n,\ i\neq j\) do

for \(k=1,2,\dots,n,\ k\neq j\) do

\(d_{ik}:=\min\{d_{ik},d_{ij}+d_{jk}\}\)

end .

Floydov-Warshallov algoritmus pre problém najkratšej cesty má zložitosť \(O(|V|^3)\), teda na dosiahnutie výsledku v najhoršom prípade spotrebuje \(O(|V|^3)\) operácií. Analýza algoritmu je ľahká, pretože kľúčovým pozorovaním je fakt, že algoritmus obsahuje tri zahniezdené slučky (cykly), pričom každá z nich je vykonávaná v čase \(O(|V|)\).
Zobraziť riešenie Skryť riešenie

Zdroje

Algoritmy a zložitosť

Doplňujúce úlohy

Úloha: Popíšte metódu na odčítanie decimálnych prirodzených čísel ako algoritmus.

Úloha: Zostrojte algoritmus pre nasledujúci problém:
Je daný graf \( G=(V,E) \). Existuje v \( G \) cyklus \( (u,v,w,z,u) \) taký, že \( (v,z),\ (u,w)\not\in E \), pričom

\( u,v,w,z \) sú ľubovoľné vrcholy,
\(u,v,w,z \) sú pevne dané?

Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.

Úloha: Zostrojte algoritmus pre nasledujúci problém:
Pre dané \( p\in N \) rozhodnite, či \( p \) je prvočíslo.
Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.

Úloha: Zostrojte algoritmus pre nasledujúci problém:
Pre dané \( x,y,z \in N \) rozhodnite, či existuje \( n>0,\ n\in N \) také, že platí: \( x^n+y^n=z^n. \)
Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.

Úloha: Zostrojte algoritmus pre nasledujúci problém: Daný je graf \( G=(V,E) \) a \( s,t\in V \). Existuje v \(G \) cesta z vrchola \( s \) do vrchola \( t \)?
Fixujte reprezentáciu vstupu a popíšte zložitosť navrhnutého algoritmu.