Chinaunix

标题: 替换法,推导递归方程遇到问题 [打印本页]

作者: willaty 时间: 2016-05-31 09:04
标题: 替换法,推导递归方程遇到问题
我的递归推导:
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))[T(1)+u(n)], 其中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是不断被换的呀?

可能存在某个替换技巧我没有使用.

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)