Rozwiązywanie rekurencji

Przekształcając rekurencję:
$T(n) = 2T(\lfloor \sqrt{n} \rfloor) + log_2n$

otrzymuję:

$T(2^m) = 2T(2^{m/2}) + m$ , gdzie m = log₂n

Jednakże w kolejnym kroku, gdzie S(m) = T(2^m)

$S(m) = 2S(m/2) + m$

przekształcenie nie jest dla mnie zrozumiałe. Mógłby ktoś wspomóc skąd wzięło się S(m) = T(2^m) ?

Jeżeli S(m) = T(2^m), to kładąc w tym wzorze m = m/2 Otrzymujesz powyższe przejście.

Mógłbyś to bardziej rozpisać?
Bo nie rozumiem dlaczego S(m) = T(2^m).

Podając przykładowo za m = 4, otrzymuję S(4) = T(16), co rozpisując:
$S(4) = 2S(2) + 4$
$T(16) = 2T(4) + 4$

Skąd ta wynika różnica?

Przecież nie wiem co to jest S(m), natomiast z założenia S(m) = T(2^m) wynika przejście z Twojego wzoru 2 do 3.

Ok, wszystko jasne, dzięki.

Liczba odpowiedzi na stronę