Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami

'''Twierdzenie o rekurencji uniwersalnej''' jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować [[ograniczenie asymptotyczne]] pewnej klasy [[Funkcja (matematyka)|funkcji]] zdefiniowanych [[Rekurencja|rekurencyjnie]].

 

 

 

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 \lg\ n)</math>

 

Tak zdefiniowane funcje ''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.

 

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".

 

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''' mniejszoś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.

 

Niech ''n'' będzie [[potęga (matematyka)|potęgą]] liczby rzeczywistej ''b'', takiej, że <math>b>1</math>

Niech zmienne ''a'', ''b'' i funkcja ''f'' będą zdefinowane jak powyżej. Jeśli dla pewnej dodatniej liczby całkowitej ''i'' funkcja ''T'' jest zdefinowana następująco:

 

T(\frac{n}{b}) + f(n)&:n\ =\ b^i \end{matrix} \right.</math>

 

to

 

 

Rozważmy [[drzewo rekursji]] funkcji ''T'' zdefiniowanej jak wyżej.

 

* 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''.

 

 

Sumując koszty wszystkich poziomów drzewa otrzymamy równanie (*), ponieważ koszt wszystkich "poziomów" węzłów właściwych (tj. nie bę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>

 

Niech ''a'', ''b'' i ''f'' będą określone jak powyżej. Jeżeli ''g'' jest funkcją określoną dla ''n'' będących potęgami ''b'' w następujący sposób:

 

 

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 \ln\ n)</math>

 

Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolenych przypadków z lematu 2 zachodzi:

 

* <math>\! T(n)\ =\ \Theta (n^{log_ba})\ +\ O(n^{log_ba})\ =\ \Theta(n^{log_ba})</math>

 

 

 

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

 

 

i

 

 

 

Równanie rekurencyjne można oszacować z góry w następujący sposób:

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów <math>\! n[0],\ n[1],\ n[2],\ \cdots</math>

 

 

 

* <math>\cdots </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.