递归式与分治方法是紧密相关的，因为使用递归式可以清晰的刻画分治算法的运行时间。
主方法如下：
T(n) = aT(n/b) + f(n)
a>=1 b>1 f(n) 是给定的函数。这种形式的递归式很常见。刻画了一个分治算法。生成a个子问题。每个子问题是原来的1/b。分解和合并步骤共消耗f(n)
主方法是计算时间复杂度的时候用的。
利用上面的这个定理就可以计算递归式的时间复杂度了，这里面的1）与3）换句话说就是1)f(n)
nlogb^a
T（n） = 9T(n/3) + n 那么计算其渐进界就是nlog3^9=n^2
阅读(14947) | 评论(0) | 转发(0) |
