Určovanie počtu operácií v rekurzívnych volaniach: Rozdiel medzi revíziami

Verzia z 13:52, 25. marec 2025

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{aligned} T (n) & = T (n - 1) + 5 \\ T (1) & = 3 \end{aligned}$

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{aligned} 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{aligned}$

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{aligned} T (n) & = T (n - 1) + 5 \\ T (n - 1) & = ? \end{aligned}$

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{aligned} T (n) & = T (n - 1) + 5 \\ T (n - 1) & = T (\underset{n}{\underset{⏟}{n - 1}} - 1) + 5 \\ T (n - 1) & = T (n - 2) + 5 \end{aligned}$

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{aligned} T (n - 1) & = T (n - 2) + 5 \\ T (n - 2) & = T (n - 3) + 5 \\ T (n - 3) & = T (n - 4) + 5 \end{aligned}$

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{aligned} T (n) & = T (n - 1) + 5 \\ = T (n - 2) + 5 + 5 \\ = T (n - 3) + 5 + 5 \\ = T (n - 4) + 5 + 5 + 5 \\ \dots \end{aligned}$

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ť tento triviálny prípad:

$T (n) = \overset{sem}{\overset{⏞}{T (n - 4)}} + 5 + 5 + 5$

Musíme to ale spraviť tak, aby sa nám nestratilo $n$ (aby sme to stále mohli vyjadriť pre ľubovoľné $n$ ). Inými slovami, nemôžme spraviť jednoducho toto:

$\begin{aligned} T (n) & = T (1) + 5 + 5 + 5 \\ T (n) & = 3 + 5 + 5 + 5 ⟵ takto predsa tá funkcia definovaná nie je... \end{aligned}$

Ale, zámer zostáva rovnaký – vsunúť tam $T (1)$ , pretože toto je jediný prípad ktorý neobsahuje rekurziu. Teda nám to umožní funkciu vyjadriť nerekurzívne (analyticky). Musíme sa nad tým zamyslieť inak – ak máme nejaké $n$ , čo musíme spraviť aby sme z tohto $n$ spravili číslo 1?

Ak odčítame dve rovnaké hodnoty, dostaneme nulu. A potom stačí pripočítať 1 a máme triviálny prípad. Takže, niečo takéto by fungovalo:

$T (n) = T (\overset{toto bude vždy 3}{\overset{⏞}{n - n + 1}}) + 5 + 5 + 5$

« Určovanie počtu operácií

Asymptotická notácia »

@@ Riadok 28: / Riadok 28: @@
 Našťastie, pre tento prípad vieme rekurzívne funkcie vyjadriť analyticky (teda, nerekurzívne) – to znamená že pre dané <math>n</math> vieme vypočítať konkrétnu hodnotu bez toho, aby sme volali funkciu rekurzívne.
-Pre analýzu funkcie musíme postupovať odzadu
+Pri analýze funkcie musíme postupovať od čísla <math>n</math> a postupne sa vnárať hlbšie a hlbšie do rekurzie. Pre príklad vyššie by sme postupovali takto:
+<math display="block">\begin{align}
+T(n) &= {\color{hotpink}T(n - 1)} + 5 \\
+{\color{hotpink}T(n - 1)} &= ? \\
+\end{align}</math>
+Ako všeobecne vyjadríme <math>{\color{hotpink}T(n - 1)}</math>? Tak, že zoberieme všeobecnú definíciu funkcie <math>T(n)</math> a namiesto <math>n</math> dosadíme <math>n - 1</math>:
+<math display="block">\begin{align}
+T(n) &= T({\color{firebrick}n} - 1) + 5 \\
+{\color{hotpink}T({\color{green}n - 1})} &= T(\underbrace{\color{green}n - 1}_{\color{firebrick}n} - 1) + 5 \\
+T(n - 1) &= T(n - 2) + 5 \\
+\end{align}</math>
+To dáva zmysel – ak chceme vyjadriť <math>T(n - 1)</math>, musíme k hodnote predtým (<math>T(n - 2)</math>) pripočítať 5. Inými slovami, vždy sa hodnota pre nejaké <math>n</math> vyjadrí tak, že sa k hodnote predtým (<math>n - 1</math>) pripočíta 5. '''Ale nesmieme zabudnúť, že <math>T(1) = 3</math>'''.
+Ak by sme pokračovali vo vyjadrovaní menších a menších <math>n</math>, vyzeralo by to nejako takto. <math>n</math> znižujeme preto, lebo sa chceme priblížiť ku triviálnemu prípadu: číslu 3 (predpokladá sa, že <math>3 < n</math>):
+<math>\begin{align}
+T(n - 1) &= {\color{orange}T(n - 2) + 5} \\
+T(n - 2) &= {\color{crimsonred}T(n - 3) + 5} \\
+T(n - 3) &= {\color{green}T(n - 4) + 5} \\
+\end{align}</math>
+Teraz sme si vyjadrili pomocné funkcie a vnorili sa hlbšie do rekurzie. Tieto funkcie musíme dosadiť späť do pôvodného <math>T(n)</math>, teda:
+<math display="block">\begin{align}
+T(n) &= T(n - 1) + 5 \\
+&= {\color{orange}T(n - 2) + 5} + 5 \\
+&= {\color{crimsonred}T(n - 3) + 5}\ {\color{orange} +\ 5} \\
+&= {\color{green}T(n - 4) + 5}\ {\color{crimsonred} +\ 5}\ {\color{orange} +\ 5} \\
+\cdots \\
+\end{align}</math>
+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 '''<math>T(1) = 3</math>'''. To znamená, že funkcia nebude volať samú seba, ak <math>n = 1</math> (pretože vráti iba číslo 3).
+To znamená, že do nášho rozpisu musíme namiesto posledného rekurzívneho volania dať tento triviálny prípad:
+<math display="block">T(n) = \overbrace{\color{green}T(n - 4)}^{\text{sem}} + 5 + 5 + 5</math>
+Musíme to ale spraviť tak, aby sa nám nestratilo <math>n</math> (aby sme to stále mohli vyjadriť pre ľubovoľné <math>n</math>). Inými slovami, nemôžme spraviť jednoducho toto:
+<math display="block">\begin{align}
+T(n) &= \cancel{\color{red}T(1)} + 5 + 5 + 5 \\
+T(n) &= 3 + 5 + 5 + 5 \longleftarrow \text{takto predsa tá funkcia definovaná nie je...} \\
+\end{align}</math>
+Ale, zámer zostáva rovnaký – vsunúť tam <math>T(1)</math>, pretože toto je jediný prípad ktorý neobsahuje rekurziu. Teda nám to umožní funkciu vyjadriť nerekurzívne (analyticky). Musíme sa nad tým zamyslieť inak – ak máme nejaké <math>n</math>, čo musíme spraviť aby sme z tohto <math>n</math> spravili číslo 1?
+Ak odčítame dve rovnaké hodnoty, dostaneme nulu. A potom stačí pripočítať 1 a máme triviálny prípad. Takže, niečo takéto by fungovalo:
+<math display="block">T(n) = T(\overbrace{n - n + 1}^{\text{toto bude vždy}\ 3}) + 5 + 5 + 5</math>
 {{Téma|Oblast=Kategória:Algoritmy a výpočtová zložitosť|Poradie=25}}
 [[Kategória:Algoritmy a výpočtová zložitosť]]