算法导论中间递归一节中:
关于T(n) = aT(n/b) + f(n), a >= 1, b > 1。
此书的作者提出了一种解法(master method),分情况对于f(n),a,b三个参数对于最后解的影响做了解答。
实际上,个人认为有更好基于代数技巧的的方法。但是并不难于掌握。
set n = b^k, S(k) = T(b^k), then we have: S(k) = a S(k-1) + f(b^k), (1-1)
expand(1-1),then we can see the process below:
S(k) = a( aS(k-2) + f(b^(k-1)) ) + f(b^k)
= a^2 S(k-2) + a f(b ^ (k-1)) + f(b^k);
= ....
= a^(k-1)S(1) + a^(......
阅读全文