总目录1(时间复杂度) 分治法与时间复 杂度计算 今一理论上的可计算与现实上的可计算 今二算法时间复杂度分析 21概念、数学表示 陈长城 22时间复杂度分析 2007-10-31 ◆22.1循环 ◆222递归 总目录2(分治法) 理论上的可计算与现实上的可计算 令三分治策略 今1.1理论上的可计算 ≤主要思想、实例、总结 四递归算法与递推方程 可计算性理论 s递推方程定义、求解、实 ◆五降低递归算法复杂性的途径 今12现实上的可计算 问题个数、实例 计算复杂性理论 52预处理减少递归的操作、实例 今六各类算法比较 今七思考题 1.1理论上的可计算一一可计算性理论 研究目标 1.2现实上的可计算一一计算复杂性理论 确定什么问题是可计算的 内容 算法复杂度—算法所使用的时间、空间的估计 已有的:递归函数、 Turing机、λ演算、Post系统等 问题复杂度—估计问题的难度 条件:计算一个函数只要有限条指令 术语和概念 每条指令可以由模型中的有限个计算步暴完成 指令执行的过程是确定的 ChurchrTur ing论题 算法的时间复杂度 如果一个函数在某个合理的计算模型上可计算,那么它在 Tur ing机上也是可计算的 复杂度函数的阶 可计算性是不依赖于计算模型的客性质 多项式时间的算法与指数时间的算法 问愿的复杂度分析
1 1 分治法与时间复 杂度计算 陈长城 2007-10-31 2 总目录1（时间复杂度） 一 理论上的可计算与现实上的可计算 二 算法时间复杂度分析 \2.1概念、数学表示 \2.2时间复杂度分析 2.2.1循环 2.2.2递归 3 总目录2（分治法） 三 分治策略 \ 主要思想、实例、总结 四 递归算法与递推方程 \ 递推方程定义、求解、实例 五 降低递归算法复杂性的途径 \ 5.1代数变换减少子问题个数、实例 \ 5.2预处理减少递归的操作、实例 六 各类算法比较 七 思考题 4 一 理论上的可计算与现实上的可计算 1.1理论上的可计算 \可计算性理论 1.2现实上的可计算 \计算复杂性理论 5 1.1 理论上的可计算――可计算性理论 研究目标 确定什么问题是可计算的 合理的计算模型 已有的：递归函数、Turing 机、λ 演算、Post 系统等 条件：计算一个函数只要有限条指令 每条指令可以由模型中的有限个计算步骤完成 指令执行的过程是确定的 Church-Turing 论题 如果一个函数在某个合理的计算模型上可计算，那么它在 Turing 机上也是可计算的 可计算性是不依赖于计算模型的客观性质 6 1.2 现实上的可计算――计算复杂性理论 内容 算法复杂度——算法所使用的时间、空间的估计 问题复杂度——估计问题的难度 术语和概念 问题 算法 算法的时间复杂度 复杂度函数的阶 多项式时间的算法与指数时间的算法 问题的复杂度分析
算法的时间复杂度 高度并行可解 最坏情况下的时间复杂度 实上可解 算法求解输入规模为n的实例所需要的最长时间Wm) 平均情况下的时间复杂度 算法求解输入规模为n的实例所需妥的平均时间A(n) 理论上可解 理论上不回解 复杂度示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数 例搜囊问 复杂度函数的阶 输入:非降顺序排列的数组L,元章数为n.数x 设∫和g是定义域为自然教集N上的函数 输出:,若x在L中,j是x首次出现的序标; fn O(g(n). 否则j=0 若存在正敫c和m使得对一切心有0mcgm) 算法顺序搜囊 假设x在L中的概率为P 若存在正数c和m使得对一切mm有0sg(m)sfm) x在L中不同位置是等橛分布的, 对所有正c1存在m使得对 有0f(m)<cg(m) n)=∑2+(-p,++-Pm n)=Ogn)且fn)-oug(m) O(1)示常最函数 例设()=2n2-3n证明凡0)en2 大O表示法的常用计算规则 证若存在正数cd使得 今加法规则 sT)=71(m)+72(m)=O1()+O(2(m)= 那么企12,m1;c14,n27 O(max(f1(n), f2(n)) 取c=1/14,=12,n=7 乘法规则 例设几n)=6n,证明fn)n2) ≤7(m)=7(m)×72(m)=o1(m)×O(2(n)= o(f(m)×2(m) 证要使6n≤cm2,则6n≤ 与c是常数矛盾
2 7 8 二 算法的时间复杂度 最坏情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的最长时间 W(n) 平均情况下的时间复杂度 算法求解输入规模为 n 的实例所需要的平均时间 A(n) 复杂度表示 针对问题选择基本运算 将基本运算次数表示为输入规模的函数 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 中不同位置是等概分布的，则 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)表示常数函数 11 例 设 证明 f(n)=Θ(n2 ) 证 若存在正数 c,d 使得 那么 d≥1/2 ,n≥1; c≤1/14, n≥7 取 c=1/14, d=1/2, n0=7 例 设 f(n)=6n3 , 证明 f(n)≠ Θ(n2 ) 证 要使 6n3 ≤cn2 ，则 6n≤c , 即 n≤c/6, 与 c 是常数矛盾 3 , 2 1 ( ) 2 f n = n − n , 3 2 1 d n c ≤ − ≤ 12 大O表示法的常用计算规则 加法规则 \T(n) = T1(n)+ T2(n) = O(f1(n)) + O(f2(n))= O(max(f1(n), f2(n))) 乘法规则 \T(n) = T1(n)×T2(n) = O(f1(n))×O(f2(n))= O(f1(n)×f2(n))
多项式时间的算法与指数时间的算法 多项式时间的算法 时间复杂度函数为OU(m)的算法,其中pn是n的多项式 指时间的算法 不存在多项式P(m)使得该算法的时间复杂度为Op(n) 810|27*10364·103125·10 中每等9{8998 I"x243L7分52分130 211吩卫天世 Figure 2.24 Plot of various functions 3秒刻分《年35世21世氮[L31“世起 小时可解的问题实例的最大横 22时间复杂度分析 计机快100倍的计算机快100倍的计算机 多项式时间可解的问题与难解的问题 1000N 10N2 多项式时间可解的问题P 存在着解P的多项式时间的算法 4.64N3 N3 难解的问题P 3.98N4 不存在解P的多项式时间的算法 Ns N+6.64 N4+9.97 实际上可计算的问题 多项式时间可解的问题 N+419 N+6.29 22时间复杂度分析 2.2.1循环 今算法的执行时间绝大部分花在循环和递归 ◆循环语句的时间代价一般用以下三条原则分析 上,现分别讨论 s对于一个循环,循环次数乘以每次执行循环体内的简单 循环 语句的数目即为其时间代价 对于多个并列循环,可先计算每个循环的时间代价,然 后按大O表示法的加法规则计算总代价 对于多层嵌套循环,一般可按大O表示法的乘法规则计 算。但如果嵌套是有条件的,为精确计算其时间代价 要仔细累加循环中简单语句的实际执行数目,以确定其 时间代价
3 13 .059秒 58分 6.5年 3855世纪 2*108世纪 1.3*1013世纪 14 3n 2n .001秒 1.0秒 17.9分 12.7天 35.7年 366世纪 n5 10-1 3.2 24.3 1.7分 5.2分 13.0分 216*10-3 125*10-3 64*10-3 27*10-3 8*10-3 10-3 n3 36*10-4 25*10-4 16*10-4 9*10-4 4*10-4 10-4 n2 6*10-5 5*10-5 4*10-5 3*10-5 2*10－5 10－5 n 10 20 30 40 50 60 时间复杂 问题规模 度函数 多项式时间的算法与指数时间的算法 多项式时间的算法 时间复杂度函数为 O(p(n))的算法，其中 p(n)是 n 的多项式 指数时间的算法 不存在多项式 p(n)使得该算法的时间复杂度为 O(p(n)) 15 N6 N + 6.29 6 N + 4.19 3 6 n N5 N + 9.97 5 N + 6.64 2 5 n 3.98 N4 n N4 2.5 N4 5 10 N3 n N3 4.64 N3 3 31.6 N2 n N2 10 N2 2 1000 N1 n N1 100 N1 计算机 快100倍的计算机 快1000倍的计算机 时间复杂 1小时可解的问题实例的最大规模 度函数 16 2.2 时间复杂度分析 多项式时间可解的问题与难解的问题 多项式时间可解的问题 P 存在着解 P 的多项式时间的算法 难解的问题 P 不存在解 P 的多项式时间的算法 实际上可计算的问题 多项式时间可解的问题 17 2.2 时间复杂度分析 算法的执行时间绝大部分花在循环和递归 上，现分别讨论 \循环 \递归 18 2.2.1 循环 循环语句的时间代价一般用以下三条原则分析 \对于一个循环，循环次数乘以每次执行循环体内的简单 语句的数目即为其时间代价 \对于多个并列循环，可先计算每个循环的时间代价，然 后按大Ｏ表示法的加法规则计算总代价 \对于多层嵌套循环，一般可按大Ｏ表示法的乘法规则计 算。但如果嵌套是有条件的，为精确计算其时间代价， 要仔细累加循环中简单语句的实际执行数目，以确定其 时间代价
222递归 总目录2(分治法 写出递推方程 ◆三分治策略 主要思想、实例、总结 求解递推方程 今四递归算法与递推方程 五 推方程定义、求解、实例 低递归算法复杂性的途径 详见本讲义第四部分 52预处理减少递归的操作、实例 六各类算法比较 七思考题 分治思想在生活中普遍存在 归并排序 所谓分而治之,如 今归并排序是大家十分熟悉的一种排序算法 今社会分工分工斤活/整体 今但是,大家有没有思考过导致归并算法高效 今扑克牌分拣分工/分拣/合 的本质原因是什么呢? 今好了,假设我们现在都不知道什么是归并排 今下面我们一起看看“归并排序”这个算法 序,让我们来把它“设计”出来! 今归并排序从头说 考虑排序 分而治之 今对于单独的一个元素,不需要做任何比较和移动 今对于n个元素,恩,看上去比较复杂。 它已经有序了 今何不把它分成两个部分,先把两部分分别解决了 今对于两个元素,进行一次比较和最多一次移动,便 再想办法将这两部分合并起来呢? 能将它们排序; n个元素分成两半,每半最多只有[n2]+1个元素 今对于三个元素,三次比较,最多两次移动,便能将 当n>2时,[n2]+1<n,数据的规模每次分配都会减 小,而且可以预见,最终将会缩小到只剩1个或者2 今对于n个元素呢? 今1个或者2个元素的排序!呵呵
4 19 2.2.2 递归 写出递推方程 求解递推方程 详见本讲义第四部分 20 总目录2（分治法） 三 分治策略 \ 主要思想、实例、总结 四 递归算法与递推方程 \ 递推方程定义、求解、实例 五 降低递归算法复杂性的途径 \ 5.1代数变换减少子问题个数、实例 \ 5.2预处理减少递归的操作、实例 六 各类算法比较 七 思考题 21 分治思想在生活中普遍存在 所谓分而治之，如 社会分工 分工/干活/整体 扑克牌分拣 分工/分拣/合一 下面我们一起看看“归并排序”这个算法 22 归并排序 归并排序是大家十分熟悉的一种排序算法 但是，大家有没有思考过导致归并算法高效 的本质原因是什么呢？ 好了，假设我们现在都不知道什么是归并排 序，让我们来把它“设计”出来！ 归并排序从头说… 23 考虑排序… 对于单独的一个元素，不需要做任何比较和移动， 它已经有序了； 对于两个元素，进行一次比较和最多一次移动，便 能将它们排序； 对于三个元素，三次比较，最多两次移动，便能将 它们排序； …… 对于n个元素呢？ 24 分而治之… 对于n个元素，恩，看上去比较复杂。 何不把它分成两个部分，先把两部分分别解决了， 再想办法将这两部分合并起来呢？ n个元素分成两半，每半最多只有[n/2]+1个元素， 当n>2时，[n/2]+1<n，数据的规模每次分配都会减 小，而且可以预见，最终将会缩小到只剩1个或者2 个元素！ 1个或者2个元素的排序！呵呵
并” 分治法 今别太得意,才想了一半呢! 今在我们把归并排序“想”出来的过程当中,用到 ◆怎么把两个有序的子序列合并成一个有序序列呢? 了这样三个思想 今这个不难,用一个临时数组,将两个有序子序列中 分—将问题分解为规模更小的子问题 的元素按大小依次倒进去就好了。时间复杂度为 治——将这些规模更小的子问题逐个击破 O(n -将已解决的子问题合并,最终得出“母”问 令这样我们就从简单到复杂把归并排序设计出来了! 题的解。 今事实上,这便是分治思想了!怎么样?一点 也不神奇吧~ 定义 分、治、合 今对于一个规模为n的问题,若该问题可以容易 今请记住这三个字 地解决(比如说规模n较小)则直接解决,否 分! 则将其分解为k个规模较小的子问题,这些子 治! 问题互相独立且与原问题形式相同,递归地 合! 解这些子问题,然后将各子问题的解合并得 到原问题的解。这种算法设计策略叫做分治 法。 令这就是分治算法的精髓所在!一定要把握 实例1:统计逆序对 解答 ◆“统计逆序对个数 令朴素的O(n2)的算法 始给n个数a1,a2an 为自呼+则称这样的元素对 今既然在讲分治,当然应该用往分治方向想 如果存在存在a 统计这n个数中逆序对的总数 今下面我们来看看怎么利用分治算法更高效地 比如说,n=5,a1到a5分别为53143 解决这道题。 则逆序对有 <53>,<5,1>,<54>,<5,3><3,1>,43>共6对
5 25 “并”… 别太得意，才想了一半呢！ 怎么把两个有序的子序列合并成一个有序序列呢？ 这个不难，用一个临时数组，将两个有序子序列中 的元素按大小依次倒进去就好了。时间复杂度为 O(n)。 这样我们就从简单到复杂把归并排序‘设计’出来了！ 26 分治法 在我们把归并排序“想”出来的过程当中，用到 了这样三个思想： \分——将问题分解为规模更小的子问题； \治——将这些规模更小的子问题逐个击破； \合——将已解决的子问题合并，最终得出“母”问 题的解。 事实上，这便是分治思想了！怎么样？一点 也不神奇吧~ 27 定义 对于一个规模为n的问题，若该问题可以容易 地解决（比如说规模n较小）则直接解决，否 则将其分解为k个规模较小的子问题，这些子 问题互相独立且与原问题形式相同，递归地 解这些子问题，然后将各子问题的解合并得 到原问题的解。这种算法设计策略叫做分治 法。 28 分、治、合… 请记住这三个字： 分！ 治！ 合！ 这就是分治算法的精髓所在！一定要把握 住！ 29 实例1：统计逆序对 “统计逆序对个数” \给n个数a1,a2…an \如果存在存在ai >aj 且i<j，则称这样的元素对 <ai ,aj >为一个逆序对 \统计这n个数中逆序对的总数 \比如说，n=5，a1到a5分别为5,3,1,4,3 \则逆序对有 <5,3>,<5,1>,<5,4>,<5,3>,<3,1>,<4,3>共6对 30 解答 朴素的O(n2)的算法 既然在讲分治，当然应该用往分治方向想 啦！ 下面我们来看看怎么利用分治算法更高效地 解决这道题