替换法,推导递归方程遇到问题
我的递归推导:aT(n/b)+f(n)
a(aT(n/b^2)+f(n/b))+f(n)
...
设存在i使b^i=n,即i=logb(n),则重复上述步骤得:
a^(logb(n))T(1)+a^(logb(n)-1)f(b)+...+af(b^(n-1))+f(b^n)
而正确结果是:n^(logb(a)), 其中u(n)=∑(1到i)h(b^i), 其中h(n)=f(n)/n^(logb(a))
ps:我写的公式中默认^优先级比/高 && u(n)是个求和式.
明显:我的推导和答案,有差别.
我就特别奇怪两点:
1. 答案是怎么引入n(logb(a))的?? 推导中是a的次方.
2. 答案为什么只含f(n),替换的过程中n是不断被换的呀?
可能存在某个替换技巧我没有使用.
页:
[1]