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}
 
<math>T(n)= \begin{cases} \Theta (1) &: 1\leqslant n < b \\
a\cdot T(\frac{n}{b}) + f(n)&: n\geqslant b
\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}
 
: <math>T(n)= \begin{cases} \Theta (1) &: n=1 \\ a\cdot
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 =====
 
==== 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}
 
<math>n[i]=\begin{cases} n &: i=0 \\
\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.