107中央資工解遞迴

[JoyceTsai]

請問，

此題詳解倒數第四行的地方，為什麼取n=4^k來解遞迴？
也看不懂為什麼帶入之後會變成Xk=2xk-1+2^k

麻煩了qq

[蘇家輝]

代入4^k是為了滿足遞迴的特徵，因為4^k除4就會變成4^(k-1)，

然後因為 x(k) = 4^k

所以 x(k-1) = 4 ^ ( k-1 )，x(k-2) = 4 ^ ( k-2 )......

sqrt ( n ) = 2^k，因為在看複雜度  sqrt ( n/4 )不大於 sqrt ( n )所以後面可以不寫，

代入原式就會有那個答案

在這裡把遞迴的數列看成一般函數會比較好懂

[JoyceTsai]

了解，謝謝您！