分治法与时间复 杂度计算 陈长城 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 机上也是可计算的 可计算性是不依赖于计算模型的客观性质
1.2现实上的可计算一一计算复杂性理论 内容 算法复杂度—算法所使用的时间、空间的估计 问题复杂度——估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 复杂度函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析
6 1.2 现实上的可计算――计算复杂性理论 内容 算法复杂度——算法所使用的时间、空间的估计 问题复杂度——估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 复杂度函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析
高度并行可解 现实上可解 理论上可解 理论上不可解
7
二算法的时间复杂度 最坏情况下的时间复杂度 算法求解输入规模为n的实例所需要的最长时间Wm) 平均情况下的时间复杂度 算法求解输入规模为n的实例所需要的平均时间A(m) 复杂度表示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数
8 二 算法的时间复杂度 最坏情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的最长时间 W( n) 平均情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的平均时间 A ( n) 复杂度表示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数
例搜索问题 输入:非降顺序排列的数组L,元素数为n.数x 输出:六若x在L中,j是x首次出现的序标; 否则j=0 算法顺序搜索 假设x在L中的概率为p x在L中不同位置是等概分布的,则 w(n)=n ∑ P(n+1) +(1-p)n 十 p)n 2
9 ∑ = + − + = + − = = n i p n p n p n n p A n i W n n 1 (1 ) 2 ( 1) ( ) (1 ) ( ) 例 搜索问题 输入：非降顺序排列的数组 L，元素数为 n. 数 x 输出：j. 若 x 在 L 中，j 是 x 首次出现的序标； 否则 j = 0 算法 顺序搜索 假设 x 在 L 中的概率为 p x 在 L 中不同位置是等概分布的，则
复杂度函数的阶 设∫和g是定义域为自然数集N上的函数 f(n=o(g(n)) 若存在正数c和m使得对一切心有0≤fm)cg(n) f(m)=(g(m) 若存在正数c和h使得对一切n有0≤cg(m)≤八m) f(m)=0(g(m) 对所有正数c<1存在m使得对一切n≥1有0≤f(m)<cg(m) f(n)=⊙(g(m) f(n=O(g(n)A f(n)=2(g(n) O(1表示常数函数
10 复杂度函数的阶 设 f 和 g 是定义域为自然数集 N 上的函数 f(n)=O(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤f(n)≤cg(n) f(n)= Ω(g(n)). 若存在正数 c 和 n0使得对一切 n≥n0有 0≤cg(n)≤ f(n) f(n)=o(g(n)). 对所有正数 c<1 存在 n0使得对一切 n≥n0有 0≤f(n)<cg(n) f(n)=Θ(g(n)) f(n)=O(g(n)) 且 f(n)=Ω(g(n)) O(1)表示常数函数