分治法与时间复 杂度计算 陈长城 2007-1031
1 分治法与时间复 杂度计算 陈长城 2007-10-31
总目录1(时间复杂度) 一理论上的可计算与现实上的可计算 今二算法时间复杂度分析 2.1概念、数学表示 22时间复杂度分析 2.2.1循环 2.2.2递归
2 总目录1（时间复杂度） 一 理论上的可计算与现实上的可计算 二 算法时间复杂度分析 \2.1概念、数学表示 \2.2时间复杂度分析 2.2.1循环 2.2.2递归
总目录2(分治法) 令三分治策略 s主要思想、实例、总结 四递归算法与递推方程 递推方程定义、求解、实例 令五降低递归算法复杂性的途径 51代数变换减少子问题个数、实例 52预处理减少递归的操作、实例 六各类算法比较 令七思考题
3 总目录2（分治法） 三 分治策略 \ 主要思想、实例、总结 四 递归算法与递推方程 \ 递推方程定义、求解、实例 五 降低递归算法复杂性的途径 \ 5.1代数变换减少子问题个数、实例 \ 5.2预处理减少递归的操作、实例 六 各类算法比较 七 思考题
理论上的可计算与现实上的可计算 1.1理论上的可计算 s可计算性理论 ÷1.2现实上的可计算 计算复杂性理论
4 一 理论上的可计算与现实上的可计算 1.1理论上的可计算 \可计算性理论 1.2现实上的可计算 \计算复杂性理论
1.1理论上的可计算一一可计算性理论 研究目标 确定什么问题是可计算的 合理的计算模型 已有的:递归函数、 TUring机、λ演算、Post系统等 条件:计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的 Church- Tur ing论题 如果一个函数在某个合理的计算模型上可计算,那么它在 Tur ing机上也是可计算的 可计算性是不依赖于计算模型的客观性质
5 1.1 理论上的可计算――可计算性理论 研究目标 确定什么问题是可计算的 合理的计算模型 已有的：递归函数、Turing 机、 λ 演算、Post 系统等 条件：计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的 Church-Turing 论题 如果一个函数在某个合理的计算模型上可计算，那么它在 Turing 机上也是可计算的 可计算性是不依赖于计算模型的客观性质