我的递归推导:
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) 是个求和式.
明显:我的推导和答案,有差别.
我就特别奇怪两点:
答案是怎么引入
n(logb(a))的?? 明明推导中是a的次方.答案为什么只含
f(n), 替换的过程中n是不断被换的呀?
可能存在某个替换技巧我没有使用.