Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Wycofano ostatnią zmianę treści (wprowadzoną przez 217.172.253.168) - jedna stała ma dwa oznaczenia |
m lit. |
||
Linia 5:
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\\
a\cdot T(\frac{n}{b}) + f(n)&: n\geqslant b \end{cases}</math>
Linia 26:
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ą
: <math>T(n)= \begin{cases} \Theta (1) &: n=1 \\ a\cdot
T(\frac{n}{b}) + f(n)&:n=b^i \end{cases}</math>
Linia 36:
===== 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 83:
Równanie rekurencyjne można oszacować z góry w następujący sposób:
Niech
<math>n[i]=\begin{cases}
\left\lceil \frac{n[i-1]}{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>T(n) = T(\left\lceil \frac{n}{b} \right\rceil) = T(\left\lceil \frac{\left\lceil \frac{n}{b}
Korzystając z nierówności <math>\left\lceil a \right\rceil \leqslant a + 1</math> mamy:
Linia 99:
* <math>n[3] \leqslant \frac{n}{b^3} + \frac{1}{b^2} + \frac{1}{b} + 1</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>
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.
| |||