Złożoność równania rekurencyjnego

komornik
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 3 paź 2007, o 22:01
Płeć: Mężczyzna
Lokalizacja: Włoszczowa

Złożoność równania rekurencyjnego

Post autor: komornik »

\(\displaystyle{ T(1)=1}\)
\(\displaystyle{ T(n)=T(\lfloor \sqrt{n} \rfloor)+ \lfloor \sqrt{n} \rfloor}\)
Proszę o pomoc z takim zadaniem, a przynajmniej o podpowiedź, jak się za nie zabrać.

Mam rozwiązanie zadania rekurencyjnego
\(\displaystyle{ T(n)=T(\lfloor n/2 \rfloor)+T(\lceil n/2 \rceil)+cn}\)
z warunkiem końcowym
\(\displaystyle{ T(1)=0}\)
i tutaj do rozwiązania wykorzystuje się podstawienie \(\displaystyle{ n=2^k}\). Chodzi mi głównie o to, skąd bierze się to podstawienie i jakie podstawienie zrobić w pierwszym zadaniu.

Dzięki!
ODPOWIEDZ