Mam do rozwiązania następujące równanie rekurencyjne:
\(\displaystyle{ T(1) = 0}\)
\(\displaystyle{ T(n) = 2T(n/2) + \Theta(n^2)}\)
I podchodzę do tego tak
\(\displaystyle{ T(n)=\sum_{n=0}^{{\log_2n}}2^i \Theta\left(\frac{n^2}{2^{2i}}\right)}\)
Nie jestem przekonany o swoim postępowaniu, czy dobrze walczę z tymi równaniami asymptotycznymi, dlatego proszę o sprawdzenie i poprawienie w razie czego.
\(\displaystyle{ \sum_{n=0}^{{\log_2n}}2^i \Theta\left(\frac{n^2}{2^{2i}}\right)=n^2\sum_{n=0}^{{\log_2n}} \Theta\left(\frac{2^i}{2^{2i}}\right)=n^2\sum_{n=0}^{{\log_2n}} \Theta\left(\frac{1}{2^{i}}\right)=n^2\cdot O(1) = \Theta(n^2)}\)
[Teoria złożoności] Rozwiązanie równania rekurencyjnego
- sebnorth
- Użytkownik
- Posty: 635
- Rejestracja: 12 sty 2011, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Puck i Trójmiasto
- Pomógł: 201 razy
[Teoria złożoności] Rozwiązanie równania rekurencyjnego
też mi wyszła złożoność kwadratowa(taka wychodzi też z trzeciego przypadku twierdzenia o rek. uniwersalnej):
\(\displaystyle{ \frac{T(n)}{n} = \frac{T( \frac{n}{2} )}{ \frac{n}{2} } + \Theta(n)}\)
dla \(\displaystyle{ n=2^m}\) dostajemy:
\(\displaystyle{ \frac{T(2^m)}{2^m} = \frac{T(2^{m-1})}{2^{m-1}} + \Theta(2^m) =}\)
\(\displaystyle{ = \frac{T(2^{m-2})}{2^{m-2}} + \Theta(2^m + 2^{m-1}) =}\)
\(\displaystyle{ = 0 + \Theta(1 + 2 + \ldots 2^m + 2^{m-1}) = \Theta(2^m)}\)
czyli \(\displaystyle{ T(2^m) = 2^m \cdot \Theta(2^m)}\)
\(\displaystyle{ T(n) = n \cdot \Theta(n) = \Theta(n^2)}\)
\(\displaystyle{ \frac{T(n)}{n} = \frac{T( \frac{n}{2} )}{ \frac{n}{2} } + \Theta(n)}\)
dla \(\displaystyle{ n=2^m}\) dostajemy:
\(\displaystyle{ \frac{T(2^m)}{2^m} = \frac{T(2^{m-1})}{2^{m-1}} + \Theta(2^m) =}\)
\(\displaystyle{ = \frac{T(2^{m-2})}{2^{m-2}} + \Theta(2^m + 2^{m-1}) =}\)
\(\displaystyle{ = 0 + \Theta(1 + 2 + \ldots 2^m + 2^{m-1}) = \Theta(2^m)}\)
czyli \(\displaystyle{ T(2^m) = 2^m \cdot \Theta(2^m)}\)
\(\displaystyle{ T(n) = n \cdot \Theta(n) = \Theta(n^2)}\)