Równanie rekurencyjne (algorytmy)

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Halmoth
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 22 maja 2012, o 21:27
Płeć: Mężczyzna
Lokalizacja: Ol
Podziękował: 5 razy

Równanie rekurencyjne (algorytmy)

Post autor: Halmoth »

Potrzebuję pomocy z przedmiotu o nazwie: Algorytmy i Struktury Danych.

Zadanie wydaje się banalne ale zupełnie nie wiem jak się do niego zabrać, oto treść:

Rozwiąż równanie rekurencyjne (dowolna metoda):

\(\displaystyle{ T\left( n\right) = 4 T\left( \frac{n}{4} \right) + n^{2}}\)
pawellogrd
Użytkownik
Użytkownik
Posty: 844
Rejestracja: 19 lis 2009, o 15:03
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 121 razy
Pomógł: 156 razy

Równanie rekurencyjne (algorytmy)

Post autor: pawellogrd »

Problem w tym, że nie podałeś całej treści zadania. Powinieneś mieć też podaną wartość \(\displaystyle{ T(0)}\) albo \(\displaystyle{ T(1)}\) albo dla jakiegokolwiek innego argumentu powinieneś mieć określoną konkretną wartość. Bez niej nie ruszymy.

Założę więc, że \(\displaystyle{ T(n)=1}\) dla \(\displaystyle{ n \le 1}\), żeby w ogóle ruszyć.

Wtedy dla \(\displaystyle{ n > 1}\):

\(\displaystyle{ T\left( n\right) = 4 T\left( \frac{n}{4} \right) + n^{2} = 4\left( 4T\left( \frac{\frac{n}{4}}{4}\right) + \left( \frac{n}{4}\right)^2 \right) + n^2 = \\ 4^2 T\left( \frac{n}{16}\right) + \frac{n^2}{4^1} + \frac{n^2}{4^0} = 4^3 T\left( \frac{n}{64}\right) + \frac{n^2}{4^2} + \frac{n^2}{4^1} + \frac{n^2}{4^0} = T(n \le 1) + ... + \frac{n^2}{4^2} + \frac{n^2}{4^1} + \frac{n^2}{4^0} = \\ \underbrace{1 \cdot 4^{\lceil \log_{4}\left( n\right) \rceil} + ... + \frac{n^2}{4^2} + \frac{n^2}{4^1} + \frac{n^2}{4^0}\right)^2}_{\lceil \log_{4}\left( n\right) \rceil + 1 \mbox{ składników}} = \\ 4^{\lceil \log_{4}\left( n\right) \rceil} + \frac{n^2}{4^{\lceil \log_{4}\left( n\right) \rceil-1} } + ... + \frac{n^2}{4^2} + \frac{n^2}{4^1} + \frac{n^2}{4^0} = \\ 4^{\lceil \log_{4}\left( n\right) \rceil} + \left( \frac{n^2}{4^{\lceil \log_{4}\left( n\right) \rceil-1} } + ... + \frac{n^2}{4^2} + \frac{n^2}{4^1} + \frac{n^2}{4^0}\right)}\)

To, ujęte w nawias, jest ciągiem geometrycznym o ilorazie \(\displaystyle{ q=\frac{1}{4}}\). Suma takiego ciągu będzie wynosić: \(\displaystyle{ S_n = \frac{a_1(1-q^n)}{1-q} = \frac{n^2\left( 1-\left( \frac{1}{4}\right)^n \right) }{1-\frac{1}{4}} = \frac{4n^2\left( 1-\frac{1}{4^n}\right) }{3}}\)

Wstawiając tą sumę w miejsce powyższego nawiasu dostajemy ostateczną postać na \(\displaystyle{ T(n)}\) dla \(\displaystyle{ n>1}\):

\(\displaystyle{ T(n)= 4^{\lceil \log_{4}\left( n\right) \rceil} + \frac{4n^2\left( 1-\frac{1}{4^n}\right) }{3}}\)

EDIT: Widzę, że odpowiedź się różni nieco od poniższej, istotne jest, jaka była pełna treść zadania. Wtedy możesz zweryfikować nasze odpowiedzi dla kilku wybranych \(\displaystyle{ n}\), np. dla \(\displaystyle{ n=1}\), \(\displaystyle{ n=4}\), \(\displaystyle{ n=16}\)
Ostatnio zmieniony 20 lis 2012, o 23:37 przez pawellogrd, łącznie zmieniany 2 razy.
Pancernik
Użytkownik
Użytkownik
Posty: 634
Rejestracja: 3 mar 2009, o 14:03
Płeć: Mężczyzna
Lokalizacja: Ruda Śląska
Podziękował: 5 razy
Pomógł: 143 razy

Równanie rekurencyjne (algorytmy)

Post autor: Pancernik »

\(\displaystyle{ T\left(n\right)=4T\left(\frac{n}{4}\right)+n^2\\
n=4^k \quad T\left(1\right)=1\\
T\left(4^k\right)=4T\left(\frac{4^k}{4}\right)+\left(4^k\right)^2=4T\left(4^{k-1}\right)+4^{2k}\\
T\left(4^k\right)=4T\left(4^{k-1}\right)+4^{2k}=4\left(4T\left(4^{k-2}\right)+4^{2k-2}\right)+4^{2k}=4\left(4\left(4T\left(4^{k-3}\right)+4^{2k-4}\right)+4^{2k-2}\right)+4^{2k}=4\left(4^2T\left(4^{k-3}\right)+4^{2k-3}+4^{2k-2}\right)+4^{2k}=4^3T\left(4^{k-3}\right)+4^{2k-2}+4^{2k-1}+4^{2k}=4^kT\left(1}\right)+4^{2k-k+1}+\dots+4^{2k-2}+4^{2k-1}+4^{2k}=4^k+4^{k+1}+\dots+4^{2k-2}+4^{2k-1}+4^{2k}=4^k\left(1+4^1+\dots+4^{k-2}+4^{k-1}+4^{k}\right)}\)


\(\displaystyle{ 1+4^1+\dots+4^{k-2}+4^{k-1}+4^{k}}\) - suma ciągu geometrycznego
\(\displaystyle{ S_n=a_1 \frac{1-q^n}{1-q}\\
S_{k+1}=1 \cdot \frac{1-4^{k+1}}{1-4} =-3\left( 1-4^{k+1}\right)=-3+3 \cdot 4^{k+1}=12 \cdot 4^k-3}\)


\(\displaystyle{ 4^k\left(1+4^1+\dots+4^{k-2}+4^{k-1}+4^{k}\right)=4^k \cdot \left( 12 \cdot 4^k-3\right) \\
T\left(4^k\right)=4^k \left( 12 \cdot 4^k-3\right)\\
T\left(n\right)=n\left( 12 n-3\right)=12n^2-3n}\)
ODPOWIEDZ