[TPI] Równania rekurencyjne

Matej91
Użytkownik
Użytkownik
Posty: 178
Rejestracja: 6 sty 2012, o 00:37
Płeć: Mężczyzna
Lokalizacja: Zielona Góra
Podziękował: 24 razy

[TPI] Równania rekurencyjne

Post autor: Matej91 »

Podać ograniczenia dla następujących równań rekurencyjnych:

\(\displaystyle{ a) T(n)=3T( \frac{n}{3}+log _{3}n}\)
\(\displaystyle{ b) T(n)=2T(n ^{ \frac{1}{3} })+log _{3}n}\)

Proszę o pomoc w rozwiązaniu tego zadania
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

[TPI] Równania rekurencyjne

Post autor: Pancernik »

a)
\(\displaystyle{ T(n)=3T\left(\frac{n}{3}\right)+log_3n\\
n=3^k\quad\Rightarrow\quad\log_3n=k\\
T(3^k)=3T\left(\frac{3^k}{3}\right)+k=3T\left(3^{k-1}\right)+k=3\left(3T\left(3^{k-2}\right)+k-1\right)+k=3\left(3\left(3T\left(3^{k-3}\right)+k-2\right)+k-1\right)+k=3\left(3^2T\left(3^{k-3}\right)+3\left(k-2\right)+k-1\right)+k=3^3T\left(3^{k-3}\right)+3^2\left(k-2\right)+3\left(k-1\right)+k=3^3T\left(3^{k-3}\right)+3^2\left(k-2\right)+3^1\left(k-1\right)+3^0\left(k-0\right)=3^kT\left(1\right)+\sum_{i=0}^{k-1}\left(3^i\left(k-i\right)\right)=3^kT\left(1\right)+\sum_{i=0}^{k-1}\left(3^ik-3^ii\right)=3^kT\left(1\right)+\sum_{i=0}^{k-1}3^ik-\sum_{i=0}^{k-1}3^ii=3^kT\left(1\right)+k\sum_{i=0}^{k-1}3^i-\sum_{i=0}^{k-1}3^ii\\
\mbox{stałe }c\mbox{ i }d\begin{cases}\sum\limits_{i=0}^{k-1}3^i=c\\\sum\limits_{i=0}^{k-1}3^ii=d\end{cases}\\
3^kT\left(1\right)+kc-d=nT\left(1\right)+c\log_3n-d}\)


Jeśli \(\displaystyle{ T\left(1\right)=0}\) to \(\displaystyle{ nT\left(1\right)+c\log_3n-d=c\log_3n-d}\) czyli \(\displaystyle{ T\left(n\right)=\Theta\left(\log_3n\right)}\).
ODPOWIEDZ