Twierdzenie o rekurencji uniwersalnej: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
m BrokenglaSSbot poprawia LaTeX |
||
Linia 13:
:* 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 \ln\ 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})\le 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>
Linia 56:
:* 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 \ln\ 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})\le 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>
Linia 66:
* <math>\! T(n)\ =\ \Theta (n^{log_ba})\ +\ O(n^{log_ba})\ =\ \Theta(n^{log_ba})</math>
* <math>\! T(n)\ =\ \Theta (n^{log_ba})\ +\ \Theta(n^{log_ba}\cdot \ln\ n)\ =\ \Theta(n^{log_ba}\cdot \ln\ 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>
| |||