Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
Nie podano opisu zmian |
||
Linia 61:
=====Dowód=====
====Dowód====
Korzystając z oszacowania z lematu 2 dla sumy (*). Dla kolenych przypadków z lematu 2 zachodzi:
Linia 70:
* <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===
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
::<math>\! T(n)\ =\ a\cdot T(\left\lfloor \frac{n}{b} \right\rfloor )\ +\ f(n)</math> (1)
i
::<math>\! T(n)\ =\ a\cdot T(\left\lceil \frac{n}{b} \right\rceil )\ +\ f(n)</math> (2)
jest banalne do znalezienia, przy wykorzystaniu własności <math>\! \left\lfloor \frac{n}{b} \right\rfloor \ge \frac{n}{b}</math> i <math>\! \left\lceil \frac{n}{b} \right\lceil \le \frac{n}{b}</math>
Równanie rekurencyjne można oszacować z góry w następujący sposób:
Niech
<math>n[i]=\left\{ \begin{matrix} \ n &: i=0\\
\ \left\lceil \frac{n[i-1]}{b} \right\rceil &:i>0 \end{matrix} \right.</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 \le a\ +\ 1</math> mamy:
* <math>n[0] \le n</math>
* <math>n[1] \le \frac{n}{b}\ +\ 1</math>
* <math>n[2] \le \frac{n}{b^2}\ +\ \frac{1}{b}\ +\ 1</math>
* <math>n[3] \le \frac{n}{b^3}\ +\ \frac{1}{b^2}\ +\ \frac{1}{b}\ +\ 1</math>
* <math>\cdots </math>
* <math>n[i] \le \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}\ \le \ \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.
[[Kategoria:Rekursja]]
| |||