2.2时间复杂度分析 多项式时间可解的问题与难解的问题 多项式时间可解的问题P 存在着解P的多项式时间的算法 难解的问题P 不存在解P的多项式时间的算法 实际上可计算的问题 多项式时间可解的问题
16 2.2 时间复杂度分析 多项式时间可解的问题与难解的问题 多项式时间可解的问题 P 存在着解 P 的多项式时间的算法 难解的问题 P 不存在解 P 的多项式时间的算法 实际上可计算的问题 多项式时间可解的问题
2.2时间复杂度分析 算法的执行时间绝大部分花在循环和递归 上,现分别讨论 循环 s递归
17 2.2 时间复杂度分析 算法的执行时间绝大部分花在循环和递归 上，现分别讨论 \循环 \递归
2.2.1循环 令循环语句的时间代价一般用以下三条原则分析 s对于一个循环,循环次数乘以每次执行循环体内的简单 语句的数目即为其时间代价 s对于多个并列循环,可先计算每个循环的时间代价,然 后按大O表示法的加法规则计算总代价 s对于多层嵌套循环,一般可按大O表示法的乘法规则计 算。但如果嵌套是有条件的,为精确计算其时间代价, 要仔细累加循环中简单语句的实际执行数目,以确定其 时间代价
18 2.2.1 循环 循环语句的时间代价一般用以下三条原则分析 \对于一个循环，循环次数乘以每次执行循环体内的简单 语句的数目即为其时间代价 \对于多个并列循环，可先计算每个循环的时间代价，然 后按大Ｏ表示法的加法规则计算总代价 \对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计 算。但如果嵌套是有条件的，为精确计算其时间代价， 要仔细累加循环中简单语句的实际执行数目，以确定其 时间代价
2.2.2递归 写出递推方程 令求解递推方程 详见本讲义第四部分
19 2.2.2 递归 写出递推方程 求解递推方程 详见本讲义第四部分
总目录2(分治法) 令三分治策略 s主要思想、实例、总结 四递归算法与递推方程 递推方程定义、求解、实例 令五降低递归算法复杂性的途径 51代数变换减少子问题个数、实例 52预处理减少递归的操作、实例 六各类算法比较 令七思考题
20 总目录2（分治法） 三 分治策略 \ 主要思想、实例、总结 四 递归算法与递推方程 \ 递推方程定义、求解、实例 五 降低递归算法复杂性的途径 \ 5.1代数变换减少子问题个数、实例 \ 5.2预处理减少递归的操作、实例 六 各类算法比较 七 思考题