算法设计与分析Note——基础数学知识
2.1计算复杂性函数的阶
2.2和式的估计与界限
1.线性和
2.级数
3.和的界限
1.
2.
2.3 递归方程
1.递归方程例：
Merge-sort(归并)排序算法的复杂性方程：
2.求解递归方程的三个主要方法：
1.替换方法：
猜想，然后用数学归纳法证明。
①联想已知的T(n)
②猜测上下界，减少不确定性范围
③变量替换方法：
注意：细微差别的处理
2.迭代方法
循环展开递归方程，把方程转化为一个和式，然后用估计和的方法来求解。
Merge-sort(归并)排序算法的复杂性方程：
猜想，然后用数学归纳法证明。
①联想已知的T(n)
②猜测上下界，减少不确定性范围
③变量替换方法：
注意：细微差别的处理
循环展开递归方程，把方程转化为一个和式，然后用估计和的方法来求解。