【算法导论】第3、4章,增长和递归式

【3】函数的增长

3.1 渐进的记号

 Theta(N):同阶,渐进确界

O(N): 渐进上界

o(N): 渐进紧上界

Omega(N): 渐进下界

【4】递归式

三种解递归式的方法:

1、代换法

  猜测解的形式,用数学归纳法找到有效的常数,并证明。

2、递归树方法

  将递归式转换为一棵树,节点表示递归调用的代价,使用边界和方法求解递归式。

3、主方法

4.1 最大子数组问题

分治法思路:一个数组的最大子数组,有三种可能:完全在左边半个中 / 完全在右边半个中 / 跨越左右两边,

4.2 矩阵乘法的Strassen算法

4.3 用代入法求解递归式

边界条件可以设置的比较松,

必要的时候可以用变量替换法

原文地址:https://www.cnblogs.com/yesuuu/p/8672814.html