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.

Pre analýzu funkcie musíme postupovať odzadu

« Určovanie počtu operácií

Asymptotická notácia »