|
== Twierdzenie o rekurencji uniwersalnej ==
Jeżeli funkcja <math>\! T(n)</math>, dla <math>\! a\geqslant 1, b>1, n>0</math> i [[funkcja dodatnia|funkcji dodatniej]] <math>\! f</math>, jest zdefiniowana następująco:
<math>T(n)= \begin{cases} \Theta (1) &: 1\leqslant n < b\\
to:
* Jeżeli <math>\! f(n) = O(n^{\log_ba-\epsilon})</math> dla pewnej stałej <math>\! \epsilon > 0</math>, to <math>\! T(n) = \Theta (n^{\log_ba})</math>
* Jeżeli <math>\! f(n) = \Theta(n^{\log_ba})</math>, to <math>\! T(n) = \Theta (n^{\log_ba}\cdot \log n)</math>
* Jeżeli <math>\! f(n) = \Omega(n^{\log_ba+\epsilon})</math> dla pewnej stałej ε > 0 i jeżeli <math>\! a\cdot f(\frac{n}{b})\leqslant c\cdot f(n)</math> dla pewnej stałej <math>\! c \in (0,1)</math>, dla dostatecznie dużych ''n'', to <math>\! T(n)=\Theta(f(n))</math>
Tak zdefiniowane funkcje ''T'' stanowią pewien schemat działania algorytmów typu "[[dziel i zwyciężaj]]" - problem o rozmiarze <math>\! n</math> dzielony jest na <math>\! a</math> podproblemów, każdy wielkości <math>\! \frac{n}{b}</math>, funkcja <math>\! f</math> przedstawia koszt dzielenia problemu, oraz połączenia rozwiązań podproblemów.
== Intuicyjna interpretacja ==
Każdy z trzech przypadków rekurencji uniwersalnej sprowadza się do stwierdzenia, która z funkcji <math>\! n^{\log_ba}</math> i ''f'' jest "większa". Gdy znana jest odpowiedź na to pytanie, automatycznie znane jest asymptotyczne ograniczenie danej rekursji - jest nią owa "większa funkcja".
== "Dziury" rekurencji uniwersalnej ==
Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji "typu" <math>\! T(\frac{n}{b}) + f(n)</math> - pomiędzy przypadkami twierdzenia istnieją "dziury". W pierwszym przypadku funkcja ''f'' musi być '''wielomianowo''' mniejsza od <math>\! n^{\log_ba}</math>. W trzecim przypadku oprócz '''wielomianowej''' większości wymagana jest pewna "regularność", "gładkość" funkcji. Jeżeli funkcja ''f'' należy do którejś z tych funkcji dla których nie ma "wielomianowej różnicy", to twierdzenie o rekursji uniwersalnej nie pozwala znaleźć asymptotycznego oszacowania rekursji.
== Dowód twierdzenia o rekurencji uniwersalnej ==
to
: <math>\! T(n) = \Theta (n^{\log_ba}) + \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math> (*)
===== Dowód =====
Rozważmy [[drzewo rekursji]] funkcji ''T'' zdefiniowanej jak wyżej.
* Koszt korzenia drzewa wynosi ''f(n)'', a jego każdego z ''a'' synów - <math>\! f(\frac{n}{b})</math>. Dla każdego syna korzenia koszt każdego z jego ''a'' synów wynosi <math>\! f(\frac{n}{b^2})</math>. A więc istnieje dokładnie <math>a^2</math> węzłów leżących w odległości ''2'' od korzenia.
* Ogólniej, dla <math>j<b</math> istnieje <math>\! a^j</math> węzłów o koszcie <math>\! f(\frac{n}{b^j})</math> oddalonych od korzenia o odległość ''j''.
** Koszt każdego liścia wynosi <math>\! T(1) = \Theta (1)</math>, a ponieważ <math>\! \frac{n}{b^{\log_bn}} = 1</math> to każdy liść znajduje się na głębokości <math>\! \log_bn</math>. Drzewo rekursji posiada <math>\! a^{\log_bn} = n^{\log_ba}</math> liści.
Sumując koszty wszystkich poziomów drzewa otrzymamy równanie (*), ponieważ koszt wszystkich "poziomów" węzłów właściwych (tj. niebędących liśćmi) wynosi <math> \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math> a koszt liści to <math>\! \Theta (n^{\log_ba})</math>
==== Lemat 2 ====
To dla ''n'' będących potęgami ''b'' funkcję ''g'' można oszacować:
** Jeżeli <math>\! f(n) = O(n^{\log_ba-\epsilon})</math> dla pewnej stałej <math>\! \epsilon > 0</math>, to <math>\! g(n) = \Theta (n^{\log_ba})</math>
** Jeżeli <math>\! f(n) = \Theta(n^{\log_ba})</math>, to <math>\! g(n) = \Theta (n^{\log_ba}\cdot \log n)</math>
** Jeżeli <math>\! f(n) = \Omega(n^{\log_ba+\epsilon})</math> dla pewnej stałej ε > 0 i jeżeli <math>\! a\cdot f(\frac{n}{b})\leqslant c\cdot f(n)</math> dla pewnej stałej <math>\! c \in (0,1)</math>, dla dostatecznie dużych ''n'', to <math>\! g(n)=\Theta(f(n))</math>
===== Dowód =====
Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolejnych przypadków z lematu 2 zachodzi:
* <math>\! T(n) = \Theta (n^{\log_ba}) + O(n^{\log_ba}) = \Theta(n^{\log_ba})</math>
* <math>\! T(n) = \Theta (n^{\log_ba}) + \Theta(n^{\log_ba}\cdot \log n) = \Theta(n^{\log_ba}\cdot \log n)</math>
* <math>\! T(n) = \Theta (n^{\log_ba}) + \Theta(f(n)) = \Theta(f(n))</math>, ponieważ <math>\! f(n) = \Omega (n^{\log_ba + \epsilon})</math>
=== Dla dowolnych n ===
Dla dowolnych ''n'' (nie będących potęga ''b'') wartość argumentu <math>\! \frac{n}{b} </math> może oznaczać <math>\left\lfloor \frac{n}{b} \right\rfloor</math> lub <math>\left\lceil\frac{n}{b} \right\rceil</math>.
Odpowiednio górne i dolne oszacowanie dla funkcji
:: <math>\! T(n) = a\cdot T \left( \left\lfloor \frac{n}{b} \right\rfloor \right) + f(n)</math> (1)
i
:: <math>\! T(n) = a\cdot T\left(\left\lceil \frac{n}{b} \right\rceil \right) + f(n)</math> (2)
jest banalne do znalezienia, przy wykorzystaniu własności <math>\! \left\lfloor \frac{n}{b} \right\rfloor \geqslant \frac{n}{b}</math> i <math>\! \left\lceil \frac{n}{b} \right\rceil \leqslant \frac{n}{b}</math>
Równanie rekurencyjne można oszacować z góry w następujący sposób:
\left\lceil \frac{n[i-1]}{b} \right\rceil &:i>0 \end{cases}</math>
Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów <math>\! n[0],\ n[1],\ n[2],\ \cdots</math>
:: <math>\! T(n) = T(\left\lceil \frac{n}{b} \right\rceil) = T(\left\lceil \frac{\left\lceil \frac{n}{b} \right\rceil }{b} \right\rceil) = \cdots </math>
Korzystając z nierówności <math>\left\lceil a \right\rceil \leqslant a + 1</math> mamy:
Dla <math>i = \left\lfloor \log_bn \right\rfloor</math>
: <math>\! n[i] = n[\left\lfloor \log_bn \right\rfloor ] < \frac{n}{b^{\left\lfloor \log_bn \right\rfloor}} + \frac{b}{b-1} \leqslant \frac{n}{b^{\log_bn -1}} + \frac{b}{b-1} = \frac{n}{\frac{n}{b}} + \frac{b}{b-1} \in O(1)</math>
Oznacza to, że dla wywołań rekursji na poziomie co najmniej <math>n[\left\lfloor \log_bn \right\rfloor ]</math> i większych rozmiar problemu jest stały.
| 