Przekształcając rekurencję:
otrzymuję:
, gdzie m = log2n
Jednakże w kolejnym kroku, gdzie S(m) = T(2m)
przekształcenie nie jest dla mnie zrozumiałe. Mógłby ktoś wspomóc skąd wzięło się S(m) = T(2m) ?
Przekształcając rekurencję:
otrzymuję:
, gdzie m = log2n
Jednakże w kolejnym kroku, gdzie S(m) = T(2m)
przekształcenie nie jest dla mnie zrozumiałe. Mógłby ktoś wspomóc skąd wzięło się S(m) = T(2m) ?
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(2m).
Podając przykładowo za m = 4, otrzymuję S(4) = T(16), co rozpisując:
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.