Rekurencja - problem ze zrozumieniem

[Goenitz]

Proszę o pomoc w zrozumieniu następujących przykładów, bo mam problem z ich częściowym zrozumieniem. Kilka rzeczy nie jest dla mnie jeszcze jasne i wierzę że z waszą pomocą to się zmieni.

Polecenie do zadania: Rozwiąż następujące równania rekurencyjne.
a)
\(\displaystyle{ T(0)=1}\) , \(\displaystyle{ T(n)=3T(n-1)+1}\)

\(\displaystyle{ T(n)=3T(n-1)+1=T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2=3^2(3T(n-3)+1)+2=... 3^k T(n-k)+k ...=3^n T(0)+n= 3^n*1+n=3^n+n}\)

b)
\(\displaystyle{ T(1)=1}\) , \(\displaystyle{ T(n)=T( \frac{n}{2} )+n}\)
Niech \(\displaystyle{ 2^m=n}\)

\(\displaystyle{ T(2^m)=T(2^{m-1})+2^m}\)

Niech \(\displaystyle{ T(2^m)=S(m)}\)
\(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m=S(m-2)2*2^m=S(m-3)+2^m+2*2^m=S(m-3)+3*2^m=...S(m-k)+k*2^m=...S(0)+m*2^m=1+m*2^m=1+log _{2}m*n=1+m log _{2}n}\)

c)
\(\displaystyle{ T(n)=T (\sqrt{n})+1}\)
Niech \(\displaystyle{ 2^m=n}\)

\(\displaystyle{ T(2^m)=T (2^{ \frac{m}{2}} )+1}\)
Niech \(\displaystyle{ S(m)=T(2^m)}\)

\(\displaystyle{ S(m)=S( \frac{m}{2})+1}\)
Niech \(\displaystyle{ m=2 ^{p}}\)

\(\displaystyle{ S(2 ^{p})=S(2 ^{p-1})+1}\)
Niech \(\displaystyle{ V(p)=S(2^p)}\)

\(\displaystyle{ V(p)=V(p-1)+1=V(p-2)+2=V(p-3)+3=V(0)+p=p+a=log _{2}m+a=log_{2}(log_{2}n)+a}\)


Moje pytania
a)
Skąd się to wzieło \(\displaystyle{ 3^n T(0)+n= 3^n*1+n=3^n+n}\) ? Bo wcześniej za każde n powstawia się \(\displaystyle{ 3T(n-1)+1}\). Chociaż nie wiem po co. Te \(\displaystyle{ T(0)=1}\) ma na to podstawianie wpływ? Coś by zmieniło gdyby było np. \(\displaystyle{ T(1)=2}\), lub \(\displaystyle{ T(1)=1}\)?

b)
Nie wiem po co się podstawia \(\displaystyle{ 2^m=n}\), a potem \(\displaystyle{ T(2^m)=S(m)}\)?
To nie wiem skąd się wzięło \(\displaystyle{ S(0)+m*2^m=1+m*2^m=1+log _{2}m*n=1+m log _{2}n}\)

c) Tradycyjnie po co te podstawiania są S(m), V(p)? Samemu się to wymyśla? I nie wiem skąd to \(\displaystyle{ V(0)+p=p+a=log _{2}m+a=log_{2}(log_{2}n)+a}\) i te logarytmy kosmiczne?

I kulminacyjne pytanie. O co chodzi w tej całej rekurencji? Co tu wyznaczamy?

[Crizz]

I kulminacyjne pytanie. O co chodzi w tej całej rekurencji? Co tu wyznaczamy?

Nie sądzisz, że to raczej powinno być Twoje pierwsze pytanie? Jeśli rozwiązujesz zadanie, a nie wiesz, na czym ono polega, to powinieneś spodziewać się wątpliwości co do wielu rzeczy.

Mamy wzory, w których wartość funkcji dla \(\displaystyle{ n}\) określona jest wartością funkcji w innym punkcie (np. dla \(\displaystyle{ n-1}\) w podpunkcie a). Chcąc obliczyć wartość funkcji dla \(\displaystyle{ n}\), musisz znać wartośc funkcji dla \(\displaystyle{ n-1}\), a żeby znać tę wartośc, musisz znać wartość funkcji dla \(\displaystyle{ n-2}\) itd. Trochę to kłopotliwe. zadanie polega na znalezieniu wzoru funkcji w postaci zwartej (który zależy tylko od \(\displaystyle{ n}\), czyli: masz wzór, podstawiasz \(\displaystyle{ n}\), masz wynik).

Skąd się to wzieło \(\displaystyle{ 3^n T(0)+n= 3^n*1+n=3^n+n}\) ? Bo wcześniej za każde n powstawia się \(\displaystyle{ 3T(n-1)+1}\). Chociaż nie wiem po co. Te \(\displaystyle{ T(0)=1}\) ma na to podstawianie wpływ? Coś by zmieniło gdyby było np. \(\displaystyle{ T(1)=2}\), lub \(\displaystyle{ T(1)=1}\)?

Znamy tylko wartość \(\displaystyle{ T(0)}\). Chcąc nie chcąc, żeby wyliczyć wartość \(\displaystyle{ T}\) dla danego \(\displaystyle{ n}\), musimy korzystać tak długo z zależności rekurencyjnej, aż dojdziemy do \(\displaystyle{ T(0)}\), np.:

\(\displaystyle{ T(3)=3T(2)+1=3(3T(1)+1)+1=3(3(3T(0)+1)+1)+1=3(3(3\cdot 1+1)+1)+1}\)

W tym rozwiązaniu zauważono po prostu, że jak k razy skorzystamy z zależności rekurencyjnej, to otrzymamy \(\displaystyle{ T(n)=3^kT(n-k)+k}\). Dalej zauważono, ze żeby dojść do \(\displaystyle{ T(0)}\) trzeba z tej zależności skorzystać \(\displaystyle{ n}\) razy, i sprawdzili, co wtedy otrzymujemy (a otrzymujemy \(\displaystyle{ 3^nT(n-n)+n}\). Stąd \(\displaystyle{ T(n)=3^nT(0)+n}\).

[bigmen]

Wydaje mi się, że zarówno przykład a jak i b są źle obliczone.

a) \(\displaystyle{ T(n)=3T(n-1)+1=T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2 ...}\)

Powinno być: \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+4}\) itd.
a nie \(\displaystyle{ T(n)=3(3T(n-2)+1)+1=3^2 T(n-2)+2}\) itd.

Jedynka nie jest tutaj mnożona przez 3.

b) \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m=S(m-2)2*2^m ...}\)

Powinno być: \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^{m-1}+2^m}\) itd.
a nie \(\displaystyle{ S(m)=S(m-1)+2^m=S(m-2)+2^m+2^m}\) itd.

Tutaj z kolei argumentem jest \(\displaystyle{ m-1}\), więc powinno być \(\displaystyle{ 2^{m-1}}\) itd.

[Crizz]

Fakt, nie wczytałem się tak dokładnie w to rozwiązanie.

[Goenitz]

Crizz dzięki za informacje.


bigmen
Jak w przykładzie a) może być tam 4? 1+1=2.

A w przykładzie b skąd m-1 w potędze?