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

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:

a\cdot T\left(\frac{n}{b}\right) + f(n)&: n\geqslant b

* 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\left(\frac{n}{b}\right)\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.

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"„większa”. Gdy znana jest odpowiedź na to pytanie, automatycznie znane jest asymptotyczne ograniczenie danej rekursji -– jest nią owa "większa„większa funkcja"funkcja”.

== "Dziury"„Dziury” rekurencji uniwersalnej ==

Należy zdawać sobie sprawę, że twierdzenie o rekurencji uniwersalnej nie wyczerpuje wszystkich przypadków, nawet rekursji "typu"„typu” <math>T\left(\frac{n}{b}\right) + f(n)</math> -– pomiędzy przypadkami twierdzenia istnieją "dziury"„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ść"„regularność”, "gładkość"„gładkość” funkcji. Jeżeli funkcja ''f'' należy do którejś z tych funkcji dla których nie ma "wielomianowej„wielomianowej różnicy"różnicy”, to twierdzenie o rekursji uniwersalnej nie pozwala znaleźć asymptotycznego oszacowania rekursji.

a\cdot T\left(\frac{n}{b}\right) + f(n)&:n=b^i

: <math>T(n) = \Theta (n^{\log_ba}) + \sum_{j = 0}^{\log_bn-1} a^j\cdot f\left(\frac{n}{b^j}\right)</math> (*)

* Koszt korzenia drzewa wynosi ''f(n)'', a jego każdego z ''a'' synów -– <math>f\left(\frac{n}{b}\right).</math>. Dla każdego syna korzenia koszt każdego z jego ''a'' synów wynosi <math>f\left(\frac{n}{b^2}\right).</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\left(\frac{n}{b^j}\right)</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"„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\left(\frac{n}{b^j}\right)</math> a koszt liści to <math>\Theta (n^{\log_ba})</math>

:: <math>g(n) = \sum_{j = 0}^{\log_bn-1} a^j\cdot f\left(\frac{n}{b^j}\right)</math>

** 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\left(\frac{n}{b}\right)\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>

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

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

:: <math>T(n) = T\left(\left\lceil \frac{n}{b} \right\rceil\right) = T\left(\left\lceil \frac{\left\lceil \frac{n}{b} \right\rceil }{b} \right\rceil\right) = \cdots </math>

* <math>\cdots </math>

* <math>n[i] \leqslant \frac{n}{b^i} + \sum_{k = 0}^{i-1} \frac{1}{b^k} < \frac{n}{b^i} + \sum_{k = 0}^{\infty } \frac{1}{b^k} = \frac{n}{b^i} + \frac{b}{b-1}</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>