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ť náročnejšie.

Posledný krok kde sme určili že tam bude $5\times (n-1)$ môže byť zatiaľ dosť ťažké na pochopenie. Poďme preto na ďalší príklad, kde si ukážeme ako sa nad tým dá uvažovať trochu inak:

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

Vidíme, že triviálny prípad je $T(1)=0$. Poďme teda postupne vyjadrovať $T(n-1)$, $T(n-2)$, $T(n-3)$... Vždy za $n$ v pôvodnom vzorci dosadíme aktuálny argument vo funkcii ktorú vyjadrujeme:

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

Funkcie hore teraz dosádzame na miesto rekurzívnych funkcií v pôvodnom výraze $T(n)$. Inými slovami, teraz nebudeme nahrádzať jednotlivé $n$, ale rovno celé $T(...)$ funkcie namiesto ekvivalentov vyššie:

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

...a takto budeme pokračovať až po triviálny prípad – $T(1)=0$. Ale poďme skúsiť niečo iné, namiesto obyčajného nahradenia $T(n-4)$ za $T(1)$.

Majme posledný riadok v našom výpočte vyššie:

$$T(n)=T(n-4)+n-4+n-3+n-2+n-1$$

Je to skoro akoby sa nám tam rysovala naša známa aritmetická postupnosť. Posledný prvok bude určite $n-1$, tak to je aj v pôvodnej funkcii $T(n)=T(n-1)+n-1$, za týmto už nič nie je takže $n-1$ musí byť posledný prvok. Ale ktorý prvok bude prvý? Teoreticky to je $T(n-4)$, ale tu je problém – je to funkcia, nie konkrétny prvok! Ako sa bude táto funkcia rozbaľovať, tak v sebe môže mať ešte veľmi dlhú postupnosť, napríklad niečo takéto:

$$T(n)=\cdots +n-7+n-6+n-5+n-4+n-3+n-2+n-1$$

Táto postupnosť musí skončiť pri $T(1)=0$. Takže, vyzerá nejako takto:

$$T(n)=0+\cdots +n-2+n-1$$

Hmm, to vyzerá jednoduchšie, ale ešte stále nemáme možnosť, ako môžeme nerekurzívne vyjadriť aká bude dlhá postupnosť. Vráťme sa teda o krok späť, kde sme ešte mali rekurzívne volanie:

$$T(n)=T(n-4)+n-4+n-3+n-2+n-1$$

Otázka je: existuje možnosť ako dosadiť do $n-4$ aby výsledok tohto výrazu bol 1 (triviálny prípad)? Ak v matematike odčítame dve rovnaké čísla, výsledok bude 0 ($1-1=0$, $123-123=0$, $\pi -\pi =0$...). Takže, toto musí platiť aj pre $n-n=0$. Ako z nuly spravíme jednotku? No, tak že ju k nej pripočítame: $n-n+1=1$. A jednotka je náš triviálny prípad! Ideme to dosadiť, aby bolo jasné čo si pod tým predstavujeme:

$$T(n)=\stackrel{T(1)=0}{\overbrace{T(n-n+1)}}+\cdots +n-4+n-3+n-2+n-1$$

Ach, zasa tie tri bodky! Ak by tam neboli, tak by sme predsa nevedeli že aká veľká postupnosť je za triviálnym prípadom. Pretože momentálne sme povedali iba to, čo už vieme – je nejaká nula a za ňou ide postupnosť $n$ ktoré sa zakaždým znižujú menej a menej, až po $n-1$. Počkať, ale veď v pôvodnom zápise sme $n-4$ nahradili $n-n+1$ aby sme dostali triviálny prípad. Mohli by sme to spraviť aj pre tú ďalšiu $n-4$? Áno, v podstate sa jedná o dva rovnaké zápisy, takže aj výsledok musí byť v tomto prípade rovnaký. Čiže:

$$T(n)=\stackrel{T(1)}{\overbrace{T(n-n+1)}}+\stackrel{\text{predtým:}n-4}{\overbrace{n-n+1}}+\cdots +n-3+n-2+n-1$$

Aha, takže teraz v podstate dopĺňame tú postupnosť z opačného konca! Takže by to pokračovalo nejako takto:

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

Poďme vyjadriť to čo vieme vyjadriť a dosadiť čo môžeme dosadiť, aby sme si to opäť zjednodušili:

$$T(n)=\stackrel{T(1)}{\overbrace{0}}+\stackrel{\text{aritmetická postupnosť}}{\overbrace{1+2+3+\cdots +n-2+n-1}}$$

Ha! Je to postupnosť čísiel! Vidíme dokonca medzeru medzi nulou a jednotkou. To znamená, že aritmetická postupnosť je iba vyznačená časť a iba na tú môžeme aplikovať vzorec. Prvý prvok je $1$, posledný $n-1$. To znamená, že výsledná nerekurzívna funkcia bude:

$$T(n)=0+\frac{(1+(n-1))\times n)}{2}$$

Hups, čo bude v tejto postupnosti počet prvkov ($n$)? Nemôže to byť rovnaké $n$ ako z $T(n)$, pretože to nevyjadruje počet prvkov našej aritmetickej postupnosti – tá postupnosť je iba pod-súčasťou celej funkcie. Teda naozajstná otázka je: koľko je čísiel od $1$ po $n-1$? Odpoveď: $\text{horná hranica}-\text{dolná}+1$. Takže: $n-1-1+1=n-1$. Pokračujeme:

$$\begin{array}{rl}T(n)& =\cancel{0+}\frac{(1+(n-1))\times (n-1))}{2}\\ & =\frac{n\times (n-1)}{2}\\ T(n)& =\frac{n^2-n}{2}\\ \end{array}$$

A to je aj naša odpoveď – tento vzorec môžeme teda použiť pre výpočet súčtu prvých $n$ prvkov, nerekurzívne (kde prvým prvkom je nula, takže $0+1+2+3+4+\cdots$). Toto riešenie je trochu zdĺhavejšie, ale zato veľmi detailné. Dokonca sme dokázali krok po kroku ako to celé funguje bez toho aby sme museli rátať prvých $n$ konkrétnych hodnôt (čo môže niektorým pomôcť, mnohým to ale veci môže úplne skomplikovať).

Pre overenie či je naše riešenie naozaj správne, skúsme vypočítať nejakú hodnotu. Najskôr to vypočítame pomocou pôvodného rekurzívneho vzťahu a potom ich porovnáme – ak sa výsledky budú rovnať, naše riešenie je správne. Teda, povedzme že chceme vedieť hodnotu $T(5)$ (teda, $n=5$):

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

Súčet prvých 5 prvkov je teda 10 ($0+1+2+3+4=10$, takže je to v poriadku). Teraz to vypočítajme pomocou našej funkcie:

$$\begin{array}{rl}T(n)& =\frac{n^2-n}{2}\\ T(5)& =\frac{5^2-5}{2}\\ & =\frac{25-5}{2}\\ & =\frac{20}{2}\\ & =10\end{array}$$

Výsledky sa zhodujú, takže to funguje a je to v poriadku. A určite je táto funkcia omnoho rýchlejšia ako jej pôvodná rekurzívna verzia.

« Určovanie počtu operácií

Asymptotická notácia »