Równania rekurencyjne - jak to ruszyć

[bigmen]

Witam,

Od jakiegoś czasu (czyt. egzamin) prześladuje mnie problem z rozwiązywaniem równań rekurencyjnych. Co prawda równania te są z przedmiotu Algorytmy i struktury danych, ale wydaje mi się że można je podciągnąć pod kategorię w której piszę.

Temat zadania jest mniej więcej taki:
Rozwiązać równanie rekurencyjne dla \(\displaystyle{ n > 1}\), wiedząc że \(\displaystyle{ T(1) = 1}\).
1. \(\displaystyle{ T(n) = T\left( \frac{n}{4} \right) + 4}\)
2. \(\displaystyle{ T(n) = 2T\left( \frac{n}{2} \right) + 4}\)

Z tego co znalazłem w jakiś notatkach, np. w 1 przykładzie można za n podstawić \(\displaystyle{ n = 3^k}\) i wtedy wykonuje się jakieś przekształcenia i dochodzi do jakiegoś wyniku .

Jeśli ktoś wie jak to ruszyć, to czekam na pomoc.

[Crizz]

Raczej \(\displaystyle{ 4^k}\), podobnie w drugim możesz spróbować podstawić \(\displaystyle{ 2^k}\) i tak długo stosować regułę rekurencyjną, aż do wzoru trzeba będzie podstawić \(\displaystyle{ T(1)}\). Trzecie nie jest rekurencyjne i nie może zachodzić \(\displaystyle{ T(1)=1}\).

Chodzi o dokładne rozwiązanie czy o oszacowanie rzędu funkcji? Jeśli o oszacowanie rzedu funkcji, to poszukaj twierdzenia o rekurencji uniwersalnej.

[Edit] Nie było trzeciego równania przypadkiem?

[bigmen]

Aa tak, miało być 4 a nie 3.

Wydaje mi się, że chodzi o dokładne rozwiązanie. Dla przykładu, który znalazłem w notatkach: \(\displaystyle{ T(n) = 3T\left( \frac{n}{3} \right) + n}\), jako wynik wyszło: \(\displaystyle{ T(n) = n\log_3n - 3 + 3^n + n}\) (nie za dokładnie jest to rozpisane, dlatego nie mogę zrozumieć jak się to rozwiązuje).

OK. Będę próbował dalej.

PS. Tak, był 3 przykład, ale niepotrzebnie go przepisałem, bo to była zwykła funkcja, bez rekurencji.

[Crizz]

Patrz: masz \(\displaystyle{ n=4^k}\). Podstawiasz zatem: \(\displaystyle{ T(n)=T(4^k)}\). Stosujesz raz regułę rekurencyjną i dostajesz \(\displaystyle{ T(n)=T\left(\frac{4^k}{4}\right)+4=T\left(4^{k-1}\right)+4}\). Stosujesz drugi raz regułę rekurencyjną i otrzymujesz \(\displaystyle{ T(n)=T\left(\frac{4^k}{4}\right)+4= \left( T\left(\frac{4^k}{8}\right)+4 \right) +4 = \left( T\left(4^{k-2}\right)+4 \right) +4}\). Ile jeszcze kroków musisz zrobić, żeby zostało \(\displaystyle{ T(n)=((((((...(((T(1)+4)+4)...+4)+4}\)? Ile wtedy tam będzie tych czwórek do dodania, jak opuścisz nawiasy?

[bigmen]

No już chyba rozumiem o co chodzi.

Żeby zostało T(1), musi być w sumie "k" kroków. I wtedy będziemy mieć również "k" czwórek.

Więc rozwiązaniem będzie: \(\displaystyle{ T(n) = 1 + k4}\) ? Co dalej daje nam: \(\displaystyle{ T(n) = 1 + 4\log_4 n}\) ?

[Crizz]

Zgadza się.

[bigmen]

O ile pierwszy przykład udało się rozwiązać, to z drugim mam już problem.

\(\displaystyle{ T(n)=2T(n/2)+4}\)
\(\displaystyle{ n=2^k}\)
\(\displaystyle{ T(n)=2T(2^{k-1})+4}\)
\(\displaystyle{ T(n)=2(2T(2^{k-2})+4)+4}\)
\(\displaystyle{ T(n)=2(...2(2T(2^{k-k})+4)...+4)+4}\)
\(\displaystyle{ T(n)=2(...2(2 \cdot 1 +4)...+4)+4}\)

I jak to teraz rozpisać?

[abc666]

\(\displaystyle{ T(n)=2T(\frac{n}{2})+4}\)
po podstawieniu
\(\displaystyle{ n=2^k}\) dostajemy

\(\displaystyle{ T(2^k)=2T\left( \frac{2^k}{2}\right) +4=2T(2^{k-1})+4}\)

podstawiamy teraz
\(\displaystyle{ T(2^m)=S(m)}\) i dostajemy
\(\displaystyle{ S(m)=2S(m-1)+4}\)

Jest to prosta rekurencja liniowa niejednorodna. Jej rozwiązanie jest postaci \(\displaystyle{ S(m)=2^m+a}\) gdzie \(\displaystyle{ a}\) to stała.

[bigmen]

A czy to podstawienie: \(\displaystyle{ T(2^m)=S(m)}\) coś nam daje?

Po podstawieniu musimy tak czy siak, dojść do momentu:

\(\displaystyle{ S(m)=2S(m-1)+4}\)
\(\displaystyle{ S(m)=2(2S(m-2)+4)+4}\)
\(\displaystyle{ S(m)=2(2(...2S(m-m+1)+4...)+4)+4}\)
\(\displaystyle{ S(m)=2(2(...2S(1)+4...)+4)+4}\)
\(\displaystyle{ S(m)=2(2(...2 + 4...)+4)+4}\)

Nie za bardzo rozumiem jak zapisać z tego wynik ostateczny?
Dwójka będzie się powtarzać \(\displaystyle{ 2^{m-1}}\), ale nie wiem co z czwórką, ponieważ będzie mnożona przez 2 przy każdym zagłębieniu.

[abc666]

Jeśli chcesz to tak rozpisywać to rzeczywiście nic nam nie daje.

Jaką postać jawną ma rekurencja już napisałem. Jeśli nie chce się korzystać np. z metody przewidywań to można zrobić jeszcze jedno podstawienie.

\(\displaystyle{ S(m)=U(m)-4}\)
skąd
\(\displaystyle{ U(m)-4=2U(m-1)-2\cdot 4+4 \\
U(m)=2U(m-1)}\)

Czyli
\(\displaystyle{ U(m)=2U(m-1)=2\cdot 2U(m-2)=...=2^m\cdot U(0)=2^m\cdot (S(0)+4)=2^m\cdot (T(1)+4)}\)

[bigmen]

A dlaczego jest: \(\displaystyle{ S(m)=U(m)-4}\) a nie \(\displaystyle{ S(m)=U(m)+4}\) ?

Wynik który wyżej otrzymaliśmy, to: \(\displaystyle{ 2^m+4=2^k+4=n+4}\), podczas gdy Wolfram podaje \(\displaystyle{ 5n - 4}\)

[abc666]

A dlaczego jest: \(\displaystyle{ S(m)=U(m)-4}\) a nie \(\displaystyle{ S(m)=U(m)+4}\) ?

A co nam da to drugie podstawienie?

Gdzie taki wynik otrzymaliśmy? Przecież tutaj nie ma wyniku, trzeba jeszcze dokończyć. Wcześniej zapomniałem o stałej jednej powinno być \(\displaystyle{ S(m)=c\cdot 2^m+a}\).

\(\displaystyle{ U(m)=2^m\cdot (T(1)+4)}\)
wracamy z podstawieniem
\(\displaystyle{ S(m)+4=2^m\cdot (T(1)+4)\\
T(2^m)=2^m\cdot (T(1)+4)-4=2^{m}\cdot (1+4)-4=5n-4}\)

Założyłem, że T(1)=1 bo tego nigdzie nie było podane dla tego przykładu.

[bigmen]

Noo teraz się zgadza .

Nie rozumiem jedynie jak wpaść na to podstawienie: \(\displaystyle{ S(m)=U(m)-4}\)

[abc666]

\(\displaystyle{ S(m)=2S(m-1)+4}\)

Jest to równanie postaci

\(\displaystyle{ S(m)=2S(m-1)+W(m)}\)

gdzie \(\displaystyle{ W(m)}\) jest pewnym wielomianem. Tutaj wielomian jest stopnia \(\displaystyle{ 0}\) więc jeśli zrobimy podstawienie \(\displaystyle{ S(m)=U(m)+a}\) to się on nam zredukuje.

\(\displaystyle{ S(m)+a=2(S(m-1)+a)+4\\
S(m)=2S(m-1)+a+4}\)
i skoro
\(\displaystyle{ a+4\equiv 0}\) to \(\displaystyle{ a=-4}\)

Jeśli ten wielomian byłby wyższego stopnia to sprawa może się skomplikować. Wszystko zależy od tego czy pierwiastki wielomianu są też pierwiastkami równania charakterystycznego. Można zobaczyć tutaj 169728.htm#p632221 oraz tutaj 25578.htm#p112086

[bigmen]

Ok, dzięki za pomoc. Trochę mi się wszystko rozjaśniło.-- 3 wrz 2011, o 13:26 --A właśnie, jeszcze napotkałem wspomniany przypadek kiedy wielomian nie jest stopnia 0. Jak w takim razie rozwiązać taki przykład?

\(\displaystyle{ T(n)=3T(n/3)+n, T(1)=1}\)

Zapoznałem się z informacjami z podanych linków, jednak niewiele mi to pomogło :/.