Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m us. {{Integracja}} - nie ma co integrować |
m drobne techniczne |
||
Linia 3:
== 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}
\end{cases}</math> 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>
Linia 24:
=== Dla n będących potęgą b ===
Niech ''n'' będzie [[potęga (matematyka)|potęgą]] liczby rzeczywistej ''b'', takiej, że <math>b>1</math>
==== Lemat 1 ====
Niech zmienne ''a'', ''b'' i funkcja ''f'' będą zdefiniowane jak powyżej. Jeśli dla pewnej dodatniej liczby całkowitej ''i'' funkcja ''T'' jest zdefiniowana następująco:
:: <math>T(n) = \begin{cases}
a\cdot T(\frac{n}{b}) + f(n)&:n=b^i
\end{cases}</math> 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.
Linia 47:
==== Lemat 2 ====
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:
:: <math>g(n) = \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math>▼
▲: <math>g(n) = \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j})</math>
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>
Linia 71 ⟶ 66:
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)
Linia 83 ⟶ 76:
Niech
:: <math>n[i] = \begin{cases}
\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:
* <math>n[0] \leqslant n</math>
* <math>n[1] \leqslant \frac{n}{b} + 1</math>
Linia 101 ⟶ 93:
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>▼
▲: <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.
|