分治策略： 上个推送我们提过分治算法，我们简单的了解了分治的意思就是分解，解决，合并。简而言之就是把大的拆成小的，然后挨个解决，然后合并就好了，我们用分治的原因是为了减少计算量，缩短计算时间。 当子问题足够大的时候需要递归求解，我们称之为递归情况。当子问题变得足够小，不再需要递归时，我们说递归已经“触底”，进入了基本情况。 有三种求解递归式的方法，即得出算法的“Θ”或“0”渐进界的方法： 代入法：我们猜测一个界，然后用数学归纳法证明这个界是正确的。 递归树法：将递归式转换为一颗树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。 主方法：T（n）=aT（n/b） f（n） 其中a |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
