Určovanie počtu operácií v rekurzívnych volaniach

Vyjadrenie funkcie $T(n)$ analyticky (nerekurzívne), určovanie výpočtovej zložitosti v rekurzívnych funkciách.

Určenie konkrétnej hodnoty rekurzívnej funkcie výpočtovej zložitosti

Už vieme určovať výpočtovú zložitosť v metódach, ktoré nie sú rekurzívne. Ale čo ak funkcia volá samú seba? Majme napríklad funkciu $T(n)$ definovanú takto:

$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(1)& =3\\ \end{array}$

Funkcia $T(n)$ odkazuje na samú seba, pričom vieme že pre $n=1$ je hodnota číslo 3. Toto sa nazýva triviálny prípad – je to bod, v ktorom sa rekurzívne volanie zastaví. Toto bude veľmi dôležité, pretože rekurzívne funkcie sa musia skôr či neskôr zastaviť (nemôžeme ich volať donekonečna).

Aby sme si vedeli lepšie predstaviť ako rekurzívne funkcie fungujú, poďme vypočítať, akú hodnotu bude mať $T(5)$:

$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(1)& =3\\ T(2)& =T(2-1)+5=T(1)+5=3+5=8\\ T(3)& =T(3-1)+5=T(2)+5=8+5=13\\ T(4)& =T(4-1)+5=T(3)+5=13+5=18\\ T(5)& =T(5-1)+5=T(4)+5=18+5=23\\ \end{array}$

Ako vidíme, $T(5)=23$. Ide iba o postupné nahrádzanie premennej $n$, pričom ak chceme vypočítať určitú hodnotu, musíme v tomto prípade poznať aj všetky predošlé hodnoty. Avšak, čo by sa stalo ak by sme chceli vypočítať $T(1000)$? Ak by sme to počítali manuálne, trvalo by to strašne dlho. Veľmi veľké hodnoty by robili problém aj najrýchlejším počítačom, obzvlášť ak by rekurzívne volania boli komplikovanejšie.

Našťastie, pre tento prípad vieme rekurzívne funkcie vyjadriť analyticky (teda, nerekurzívne) – to znamená že pre dané $n$ vieme vypočítať konkrétnu hodnotu bez toho, aby sme volali funkciu rekurzívne.

Pri analýze funkcie musíme postupovať od čísla $n$ a postupne sa vnárať hlbšie a hlbšie do rekurzie. Pre príklad vyššie by sme postupovali takto:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(n-1)& =?\\ \end{array}$$

Ako všeobecne vyjadríme $T(n-1)$? Tak, že zoberieme všeobecnú definíciu funkcie $T(n)$ a namiesto $n$ dosadíme $n-1$:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(n-1)& =T(\underset{n}{\underbrace{n-1}}-1)+5\\ T(n-1)& =T(n-2)+5\\ \end{array}$$

To dáva zmysel – ak chceme vyjadriť $T(n-1)$, musíme k hodnote predtým ($T(n-2)$) pripočítať 5. Inými slovami, vždy sa hodnota pre nejaké $n$ vyjadrí tak, že sa k hodnote predtým ($n-1$) pripočíta 5. Ale nesmieme zabudnúť, že $T(1)=3$.

Ak by sme pokračovali vo vyjadrovaní menších a menších $n$, vyzeralo by to nejako takto. $n$ znižujeme preto, lebo sa chceme priblížiť ku triviálnemu prípadu: číslu 3 (predpokladá sa, že $3<n$):

$\begin{array}{rl}T(n-1)& =T(n-2)+5\\ T(n-2)& =T(n-3)+5\\ T(n-3)& =T(n-4)+5\\ \end{array}$

Teraz sme si vyjadrili pomocné funkcie a vnorili sa hlbšie do rekurzie. Tieto funkcie musíme dosadiť späť do pôvodného $T(n)$, teda:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ & =T(n-2)+5+5\\ & =T(n-3)+5+5\\ & =T(n-4)+5+5+5\\ \cdots \\ \end{array}$$

A takto to bude pokračovať donekonečna... Ale nie? Kedy sa rekurzia skončí? Skončí sa vtedy, keď nastane triviálny prípad. Triviálny prípad je v tomto prípade $T(1)=3$. To znamená, že funkcia nebude volať samú seba, ak $n=1$ (pretože vráti iba číslo 3).

To znamená, že do nášho rozpisu musíme namiesto posledného rekurzívneho volania dať triviálny prípad:

$$T(n)=\stackrel{\text{sem}}{\overbrace{T(n-4)}}+5+5+5$$

Vsunieme tam $T(1)$ (čo je vlastne číslo 3) pretože to je jediný prípad ktorý neobsahuje rekurziu. Vďaka tomu bude funkcia vyjadrená nerekurzívne (analyticky):

$$T(n)=\stackrel{3}{\overbrace{T(1)}}+5+5+5+\cdots$$

Posledná otázka je, že koľkokrát sa tam bude nachádzať sčítanie čísla 5. Ak sa pozrieme na pôvodné výpočty vyššie, vidíme že čísiel 5 je tam vždy o 1 menej ako $n$:

$$\begin{array}{rl}T\stackrel{n=1}{\overbrace{(1)}}& =3\\ T(2)& =T(\stackrel{n=2}{\overbrace{n-1}})+\stackrel{n-1}{\overbrace{5}}\\ T(3)& =T(\stackrel{n=3}{\overbrace{n-2}})+\stackrel{n-1}{\overbrace{5+5}}\\ T(4)& =T(\stackrel{n=4}{\overbrace{n-3}})+\stackrel{n-1}{\overbrace{5+5+5}}\\ T(5)& =T(\stackrel{n=5}{\overbrace{n-4}})+\stackrel{n-1}{\overbrace{5+5+5+5}}\\ \cdots \\ \end{array}$$

Funkciu $T(n)$ môžeme teda zapísať ako:

$$\begin{array}{rl}T(n)& =T(1)+5\times (n-1)\\ & =3+5\times (n-1)\\ & =3+5n-5\\ T(n)& =5n-2\\ \end{array}$$

Bohužiaľ, nepomôže nič iné ako iba pozrieť sa na funkciu a všimnúť si vzťah medzi $n$ a postupnosťou čísiel. Odporúčam pre rekurziu vypočítať viacero príkladov, keďže sú to veci nad ktorými sa treba zamyslieť logicky a pre netrénované oko to môže byť dosť náročné.

« Určovanie počtu operácií

Asymptotická notácia »