算法设计与分析ch2 算法分析的数学基础.pptVIP

? DB-LAB (2003) 引理7的证明 ? DB-LAB (2003) 引理7的证明 ? ? DB-LAB (2003) 引理7的证明 ? DB-LAB (2003) ? DB-LAB (2003) ? DB-LAB (2003) ? DB-LAB (2003) 递归方程: 递归方程是使用小的输入值来描述 一个函数的方程或不等式. 2.4 递归方程 递归方程例: Merge-sort排序算法的复杂性方程 T(n)=?(1) if n=1 T(n)=2T(n/2)+?(n) if n1. T(n)的解是?(nlogn) ? DB-LAB (2003) Substitution方法: Guess first, 然后用数学归纳法证明. Iteration方法: 把方程转化为一个和式 然后用估计和的方法来求解. Master方法: 求解型为T(n)=aT(n/b)+f(n)的递归方程 求解递归方程的三个主要方法 ? DB-LAB (2003) Substitution方法Ⅰ：联想已知的T(n) 例1. 求解2T(n/2 + 17) + n 2.4.1 Substitution方法 证明：用数学归纳法 ? DB-LAB (2003) Substitution方法Ⅰ： 猜测上下界，减少不确定性范围 ? DB-LAB (2003) 细微差别的处理 问题：猜测正确，数学归纳法的归纳步 似乎证不出来 解决方法：从guess中减去一个低阶项， 可能work. ? DB-LAB (2003) ? DB-LAB (2003) 避免陷阱 ? DB-LAB (2003) 变量替换方法: 经变量替换把递归方程变换为熟悉的方程. ? DB-LAB (2003) 方法： 循环地展开递归方程， 把递归方程转化为和式， 然后可使用求和技术解之。 2.4.2 Iteration方法 ? DB-LAB (2003) ? DB-LAB (2003) 2.4.3 Master method ? DB-LAB (2003) Master 定理 ? DB-LAB (2003) T(n)=?(nlogba) T(n)=?(f(n)) f(n) ?(f(n)lgn) n? n-? 对于红色部分，Master定理无能为力 ? DB-LAB (2003) ? DB-LAB (2003) Master定理的使用 ? DB-LAB (2003) Master定理的使用（续） 地 适 ? DB-LAB (2003) Master定理的证明 bi ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) 引理2的证明 ? DB-LAB (2003) 引理2的证明（续） ? DB-LAB (2003) 引理2的证明（续） ?(f(n)) ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) 引理3的证明 ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) Master定理的证明(续) ? DB-LAB (2003) Master定理的证明(续) 第二章 算法分析的数学基础 ? DB-LAB (2003) 2.1.1 同阶函数集合 2.1.2 低阶函数集合 2.1.3 高阶函数集合 2.1.4 严格低阶函数集合 2.1.5 严格高阶函数集合 2.1.6 函数阶的性质 2.1 计算复杂性函数的阶 ? DB-LAB (2003) 2.1.1 同阶函数集合 定义2.1.1 (同阶函数集合) ?(f(n))={g(n) | ?c1, c20, n0, ?nn0, c1f(n)?g(n) ?c2f(n)} 称为与f(n) 同阶的函数集合。 ? DB-LAB (2003) Example ? DB-LAB (2003) 例2 证明 证. 如果存在c1、c2 0，n0使得当n?n0 时，c1?6n3?c2 n2 。于是，当nc2 /6时， n ?c2 /6，矛盾。 Example ? DB-LAB