总目录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 解决这道题。 则逆序对有 ,,,,43>共6对
5 25 “并”… 别太得意，才想了一半呢！ 怎么把两个有序的子序列合并成一个有序序列呢？ 这个不难，用一个临时数组，将两个有序子序列中 的元素按大小依次倒进去就好了。时间复杂度为 O(n)。 这样我们就从简单到复杂把归并排序‘设计’出来了！ 26 分治法 在我们把归并排序“想”出来的过程当中，用到 了这样三个思想： \分——将问题分解为规模更小的子问题； \治——将这些规模更小的子问题逐个击破； \合——将已解决的子问题合并，最终得出“母”问 题的解。 事实上，这便是分治思想了！怎么样？一点 也不神奇吧~ 27 定义 对于一个规模为n的问题，若该问题可以容易 地解决（比如说规模n较小）则直接解决，否 则将其分解为k个规模较小的子问题，这些子 问题互相独立且与原问题形式相同，递归地 解这些子问题，然后将各子问题的解合并得 到原问题的解。这种算法设计策略叫做分治 法。 28 分、治、合… 请记住这三个字： 分！ 治！ 合！ 这就是分治算法的精髓所在！一定要把握 住！ 29 实例1：统计逆序对 “统计逆序对个数” \给n个数a1,a2…an \如果存在存在ai >aj 且i为一个逆序对 \统计这n个数中逆序对的总数 \比如说，n=5，a1到a5分别为5,3,1,4,3 \则逆序对有 ,,,,,共6对 30 解答 朴素的O(n2)的算法 既然在讲分治，当然应该用往分治方向想 啦！ 下面我们来看看怎么利用分治算法更高效地 解决这道题
分、治 合,怎么办? ◆分:类似于归并排序,我们将这n个数平均分成两 ◆“合”这一步往往比较让人头疼,分治算法效率,往 部分:a1amg元素为第一部分,anay+1an为第二 部分 ◆获利于“分和“治两步,我们现在已经知道a1am ◆治:在得到了规模较小的子问题后,我们分别“搞 对的个数 它们,求出它们的逆序对个数 ◆而a1an中逆序对,不但包括分别处于两个子序列中 ◆如果子问题元素个数仅仅一个,显然逆序对个数为0 的逆序对,还包括第一个数在aan中,第二个数 如果元素为两个,那么第一个数大于第二个数则逆序对个 若元素个数超过2个 男类序对吧)。所以我们不能把两个子序 ◆递归伺候!将它继续分治 列中逆序对的个数单纯相加来得到答案 这么合 例 令当然,我们可以通过枚举来统计“另类逆序对的个 ◆假设序列一为:1,3,5,6 数,可是时间效率 序列二为:1,2,4,7 在序列一中从小往大扫描 令呵呵,这样还不如直接来O(n2)干脆多了 扫描到3,序列二中比3小的最大数是2,因此存在两个逆序对 今但是,如果我们假设序列a1a1m和序列anmg+1a 描到5,序列二中比5小的最大数是4,因此存在三个逆序对 己经分别有序呢? 中比6小的最大数是4,同样存在三个逆序对 来说明如何在两个有序的子序列中统计“另类逆序 因为序列一是从小到大扫描,序列二中的指针也总是右移的 ◆这样仅仅扫描一遍,即m)的时间,使能统计“另类逆序对”的个数 保证有序 实例2:导线与开关 今怎么样保证序列1和序列2有序呢? ◆大家回忆一下归并排序,难道不觉得 今如图所 黑盒里头有n根导线 令黑盒有两个测试端,A端有n个接线头,每个接线 ◇籽百我速考的筒进到这里,留一点点同学 头都严格连接了黑 根导线的一端:B端是n 个开关,开关连接导线的另一端。开关可以连接 任意多根导线,但是每根导线一端只能连接一个 ◆时间复杂度将是 o(nlogn ◆我们对这个黑盒进行测试,希望能用较少的测试 次数得到它内部每根导线的连接方式
6 31 分、治 分：类似于归并排序，我们将这n个数平均分成两 部分：a1~a[n/2]元素为第一部分，a[n/2]+1~an为第二 部分 治：在得到了规模较小的子问题后，我们分别“搞 定”它们，求出它们的逆序对个数。 如果子问题元素个数仅仅一个，显然逆序对个数为0； 如果元素为两个，那么第一个数大于第二个数则逆序对个 数为1，否则为0； 若元素个数超过2个…… 递归伺候！将它继续分治。 32 合，怎么办？ “合”这一步往往比较让人头疼，分治算法效率，往 往也取决于这一步做得怎么样。 获利于“分”和“治”两步，我们现在已经知道 a1~a[n/2] 和a[n/2]+1~an中逆序对的个数。 而a1~an中逆序对，不但包括分别处于两个子序列中 的逆序对，还包括第一个数在a1~a[n/2]中，第二个数 在 a[n/2]+1~an中的逆序对（为方便，我们称这种逆序 对为“另类逆序对”吧）。所以我们不能把两个子序 列中逆序对的个数单纯相加来得到答案。 33 这么合. 当然，我们可以通过枚举来统计“另类逆序对”的个 数，可是时间效率…… 呵呵，这样还不如直接来O(n2)干脆多了 但是，如果我们假设序列a1~a[n/2]和序列a[n/2]+1~an 已经分别有序呢？ 相信大家心中有数了，下面我们用一个直观的例子 来说明如何在两个有序的子序列中统计“另类逆序 对”个数。 34 例 假设序列一为：1，3，5，6 序列二为：1，2，4，7 在序列一中从小往大扫描： \ 先扫描1，序列二中没有比1小的数； \ 扫描到3，序列二中比3小的最大数是2，因此存在两个逆序对, \ 扫描到5，序列二中比5小的最大数是4，因此存在三个逆序对 ,, \ 扫描到6，序列二中比6小的最大数是4，同样存在三个逆序对 ,, \ 共计8个“另类逆序对” 因为序列一是从小到大扫描，序列二中的指针也总是右移的。 这样仅仅扫描一遍，即O(n)的时间，便能统计“另类逆序对”的个数。 35 保证有序 怎么样保证序列1和序列2有序呢？ 大家回忆一下归并排序，难道不觉得…… 好了，这道题我就讲到这里，留一点点同学 们自我思考的空间吧☺ 时间复杂度将是O(nlogn) 36 实例2：导线与开关 如图所示，一个黑盒里头有n根导线。 黑盒有两个测试端，A端有n个接线头，每个接线 头都严格连接了黑盒内一根导线的一端；B端是n 个开关，开关连接导线的另一端。开关可以连接 任意多根导线，但是每根导线一端只能连接一个 开关。 我们对这个黑盒进行测试，希望能用较少的测试 次数得到它内部每根导线的连接方式
测试方法 今标准输出标准输入意义 开关3闭合 T1Y导线1与开关3连接 有以下两种测试方法 N导线2不与开关3连接 系准输大否反试鲁快余开买操作痿 今T3Y导线3与开关3连接 通或断开) 开关3断开 性们高是等接择人有开否在 导线2不与开关2连结 失们镥是盒肉结数彌个娶线隻与繪 ◆D313 确定黑盒内部连接 间有导线连接 朴素的思路 分治的思路 今低效的算法总是很容易想的③ 今对于一个接线头一个开关的情况,我们可以 今对于本题,我们可以每次接通一个开关,然 直接断定它们之间有导线连接 后试探所有的接线头,来看看它们之间有没 今对于两个接线头两个开关的情况,最多进行3 有导线连接。 次测试就能知道它们之间的连接情况; 今这种方法平均要n次测试才能检测出黑盒内 部导线的连接情况。 今n个接线头m个开关呢? 分治思路 复杂度分析 ◆假设n个开关编号为b1-bn,与之有导线连接的m个 接线头编号a1an 令设确定n对开关和接线头需要T(m)次操作,我 ◆分:将n个开关分为两部分,b;bm+2和b 们假设每次都能将接线头和开关均分,可以 写递推方程如下 线头我但奇认确平腰线森试长所有接 ◆T(n)=n2+n+2T(m/2),且T(1)=0 今这个方程的解T(n)= o(nlogn) 递归确 体连接方 ◆但是我们要注意到这只是平均情况,在极端 坏情况下可能退化成O(n2)。和快速排序类 今合:几乎没留下工作交给“合”。 似,我们可以在划分开关的时候随机化来避 免出现这种极端情况
7 37 测试方法 有以下两种测试方法： \ 改变第k个开关的状态（往标准输出写入一行“C k”，将在 标准输入中得到一行反馈“Y”或者“N”表示开关在操作后接 通或断开）； \ 用一个带电源和灯泡的装置接通接线头j和所有开关，测试 它们之间是否有导线连接（往标准输出写入一行“T j”将在 标准输入中得到一行反馈“Y”或者“N”表示灯亮或者不 亮）。 在我们确定了黑盒内部结构之后，我们往标准输出中写 入一行“D A1 A2…An”，表示第i个接线头与第Ai个开关 间有导线连接。 38 例子 标准输出 标准输入 意义 C 3 Y 开关3闭合 T 1 Y 导线1与开关3连接 T 2 N 导线2不与开关3连接 T 3 Y 导线3与开关3连接 C 3 N 开关3断开 C 2 Y 开关2闭合 T 2 N 导线2不与开关2连结 D 3 1 3 确定黑盒内部连接 39 朴素的思路 低效的算法总是很容易想的☺ 对于本题，我们可以每次接通一个开关，然 后试探所有的接线头，来看看它们之间有没 有导线连接。 这种方法平均要n2次测试才能检测出黑盒内 部导线的连接情况。 40 分治的思路 对于一个接线头一个开关的情况，我们可以 直接断定它们之间有导线连接； 对于两个接线头两个开关的情况，最多进行3 次测试就能知道它们之间的连接情况； …… n个接线头m个开关呢？ 41 分治思路 假设n个开关编号为b1~bn，与之有导线连接的m个 接线头编号a1~an， 分：将n个开关分为两部分，b1~b[(n+1)/2]和b [(n+1)/2]+1~bn 治：我们将开关b1~b[(n+1)/2]改变状态，试探所有接 线头，便可以确定每个接线头是与开关b1~b[(n+1)/2] 有关系还是与开关b [(n+1)/2]+1~bn连接了。然后我们 递归确定开关b1~b[(n+1)/2]和b [(n+1)/2]+1~bn具体连接方 式，除非n=2，因为开关分成两部分后各只有一 个，可以直接确定了。n=1当然也是。 合：几乎没留下工作交给“合”。 42 复杂度分析 设确定n对开关和接线头需要T(n)次操作，我 们假设每次都能将接线头和开关均分，可以 写递推方程如下： T(n)=n/2+n+2T(n/2)，且T(1)=0 这个方程的解T(n)=O(nlogn) 但是我们要注意到这只是平均情况，在极端 坏情况下可能退化成O(n2)。和快速排序类 似，我们可以在划分开关的时候随机化来避 免出现这种极端情况
二分查找 实例3:查找两个不下降序列中位数 在一个有序序列中,查找给定的元素,通常使用二分查找较 为高效 今给定两个长度为n的不下降序列a1~an, 分查找是分治算法中比较特殊的一类 b1~bn,设计一个最坏情况下时间复杂度为 ◆分:将有序序列分为相等的两半 o(ogn)的算法,找出两个序列中第n大的 今治:比较需要查找元素的关键字和序列中位数比较,如果 数,即中位数 续在较大的半段中继续查找:如果中位数较 大,则在较小的半段中查找:如果相等 今比如两序列分别为13,59和2369,合并后 址,查找成功 为1,2,3,3,5,6,9,其中第4大的数是3 ◆合:返回在自序列中查找的结果即可 分查找的时间复杂度为Oogn) 将问题变化一下 二分查找 不妨假设,两个序列合并后前n大的数包含p个序列a中的 数,q个序列b中的数 令由于p+q=n,即q=np,我们只需确定p ◆显然有p+q=n,而且a+>=b 今利用上页分析的性质,我们在序列a中进行二分查 b属于两序列合并后前n大的 n大的数,这与开始的 ≤假设当前查找区间为xy,取区间中点m=(x+y)/2] 若m满足am+1>=bnm且bnm+1>=am,那么m即为我们需要 局时想是分(-况需要付论是要条 的p,返回值 ◆于是问题变化为,寻找满足上述两个条件的p和q,中位数即 否则,若am 则在区间m1递归查找:不然, 为a。b中较大者 在区间[m+1y中递归查找 复杂度分析 特殊情况 令很显然,最多进行og2n次二分后,查找区间 ◆差点忘了提开始说的特殊情况了 将收缩为一个点。 ◆如果a,b合并后序列第n大的元素就是a或者 ◆算法的最坏时间复杂度为O(ogn bn的话,开始提及的公式就“越界”了,所以要 事先判断下: 则中位数为bn; 位数为
8 43 二分查找 在一个有序序列中，查找给定的元素，通常使用二分查找较 为高效。 二分查找是分治算法中比较特殊的一类。 分：将有序序列分为相等的两半 治：比较需要查找元素的关键字和序列中位数比较，如果中 位数较小，则继续在较大的半段中继续查找；如果中位数较 大，则在较小的半段中查找；如果相等，则返回中位数地 址，查找成功。 合：返回在自序列中查找的结果即可。 二分查找的时间复杂度为O(logn) 44 实例3：查找两个不下降序列中位数 给定两个长度为n的不下降序列a1~an， b1~bn，设计一个最坏情况下时间复杂度为 O(logn)的算法，找出两个序列中第n大的 数，即中位数。 比如两序列分别为1,3,5,9和2,3,6,9，合并后 为1,2,3,3,5,6,9，其中第4大的数是3。 45 将问题变化一下 不妨假设，两个序列合并后前n大的数包含p个序列a中的 数，q个序列b中的数。 显然有p+q=n，而且ap+1>=bq，bq+1>=ap 反证一下：如果ap+1=bq，bq+1>=ap不光是必要条 件，同时也是充分条件(有一种特殊情况需要讨论一下) 于是问题变化为，寻找满足上述两个条件的p和q，中位数即 为ap、bq中较大者。 46 二分查找 由于p+q=n，即q=n-p，我们只需确定p。 利用上页分析的性质，我们在序列a中进行二分查 找： \假设当前查找区间为[x,y]，取区间中点m=[(x+y)/2]。 \若m满足am+1>=bn-m且bn-m+1>=am，那么m即为我们需要 的p，返回值； \否则，若am+1>=bn-m，则在区间[x,m-1]递归查找；不然， 在区间[m+1,y]中递归查找。 47 复杂度分析 很显然，最多进行log2n次二分后，查找区间 将收缩为一个点。 算法的最坏时间复杂度为O(logn) 48 特殊情况 差点忘了提开始说的特殊情况了 如果a，b合并后序列第n大的元素就是an或者 bn的话，开始提及的公式就“越界”了，所以要 事先判断下： 若a1>=bn，则中位数为bn；若b1>=an，则中 位数为an
分治策略总结 划分原则 >>尽量均匀 ◆1分割分割成p个子问题。子问题间相互独立(才能分别求 今排序算法的比较 ≤问題:应该把原问题分割成多少个子问题才合适?子问题规模是否 插入排序 今于问题不均衡1 子向愿均衡1 答:需具体问题具体 定指,则 应用算法求解 W(n)=w(n-1)+n 问题:一般递归代价较大,故而有阀值m,那m如何确 W(l)=0 答:具体问题具体分析。严格数学分析,经验等。举例 W(1) →Wn)=6n) 具体问题具体分析 附0:直接插入排序 分治法能解决的问题满足的特征 ◆逐个处理待排序的记录,当Wn)=Wn)+nl 今最优 记录都已经排成序列R Wl)=0 件分治法使用的前提,大部分问题可 →Wn)=em) 签类量的解是 次比较,直到找到 位置然后插入之, 地这题之度 四递归算法与递推方程 分治策略的算法分析工具—递推方程 (m)=可f()+d(n) 当d(n)为常数时 方和初位,求fn称为解递推方a (m)-on” a≠1 两类递推方程 o( n) f(m)=∑af(n-i)+g(m) 当dn)=cn时 求解方法∫(m)=叮(7)+(n) f(n)=o(n log n) a=b 第一类推方程公式法略 第二类递撞方程选代法、邀、 Master定理
9 49 分治策略总结 1分割 分割成p个子问题。子问题间相互独立(才能分别求 解)。 \ 问题：应该把原问题分割成多少个子问题才合适？子问题规模是否 应该相同？ \ 答：需具体问题具体分析。一般来讲，均匀获得较好效果。举例。 2求解 如果子问题大于预定阈值m，则递归应用算法求解， 否则直接对子问题求解。 \ 问题：一般递归代价较大，故而有阈值m，那m如何确定。 \ 答：具体问题具体分析。严格数学分析，经验等。 举例。 3合并 \ 具体问题具体分析 50 划分原则 >>尽量均匀 排序算法的比较 \插入排序 子问题不均衡！ \归并排序 子问题均衡！ 2 W(n) = W(n-1) + n-1 W(1) = 0 ⇒ Θ W(n) = (n ) k n = 2 W(n) = 2W(n/2) + cn W(1) = 1 ⇒ Θ W(n) = (nlogn) 51 附0：直接插入排序 逐个处理待排序的记录，当 处理第k个记录时，序号i = < = O n a b O n n a b O n a b f n ab ( ) ( log ) ( ) ( ) log ( ) ( ) d(n) b n f n = af +
递归树法—迭代 r(n)=2T( n2 Master定理 例T(mn)=9T(n/3)+n a=9,b=3,f(m)=n,n3”=n2, 设a≥1,b>1为常数,f(m)为函数,T(m为非负整数 f(m)=O(m,T(m)=(m2) T(n)=aT(n/b)+f(n), 例T(n)=T(2n/3)+1 则有以下结果 =1,b=3/2,f(m)=1, 1.f(n)=O(n“)B>0,那么T(n)=e(n2) f(n)=6 2.f(m)=(n“)那么T(mn)= n"log n) ),T(n)=e(logn) 3.f(m)=m3),a>0,且对于某个常数c<1和 例T(n)=3T(n/4)+ nlog n 所有的充分大的m有(n/b)≤f(m),那么 a=3b=4,f(n)= nlogn,n如=On”), T(m)=6f(m) f(m)=Qn·),≈0.2, af(n/b)=3(n/4)log(n/4)s(3/4)nlogn=cf(n), c=3/4n充分大 计算一个数的幂 计算 Fibonacci数 定义 问题:计算a",n为自然数 if n: 传统算法:m) if F,+F 2 ifn≥2 分治 an2×an2n为偶数 0112358132134 1a2×al2×an为奇数 通常算法:从FF1,…,根据定义陆续计算 T(m)=T(m/2)+(1)→T(m)=(ogn) 时间为e(m)
10 55 递归树法——迭代 例 2 ) 2 ( ) 2 ( n n T n = T + 2 2 2 2 2 2 2 2 2 2 4 1 ) 4 ) ( 4 ) ( 4 ) ( 4 ( 2 1 ) 2 ) ( 2 ( n n n n n n n n n n $ % $ % $ % log n层 Θ（n2） 56 例 n n T n T n = T + ) + 3 2 ) ( 3 ( ) ( n n n n n n n n n n 9 4 9 2 9 2 9 3 2 3 $ % $ % $ % log 3/2 n 层 Θ(n log n) 57 Master定理 ( ) ( ( )) ( / ) ( ), 3. ( ) ( ), 0, 1 2. ( ) ( ), ( ) ( log ) 1. ( ) ( ), 0, ( ) ( ) ( ) ( / ) ( ), 1, 1 ( ) , ( ) log log log log log T n f n n af n b cf n f n n c f n n T n n n f n O n T n n T n aT n b f n a b f n T n b a b a b a b a b a = Θ ≤ = Ω > = Θ = + ≥ > + − 所有的充分大的 有 那么 且对于某个常数 和 那么 那么 则有以下结果： 设 为常数， 为函数 为非负整数 ε ε ε ε 58 例 T(n) = 9T(n / 3) + n ( ) ( ), ( ) ( ) 9, 3, ( ) , , log3 9 1 2 log3 9 2 f n O n T n n a b f n n n n = = Θ = = = = − 例 T(n) = T(2n / 3) + 1 ( ) ( ), ( ) (log ) 1, 3/ 2, ( ) 1, 1, log 1 log 1 0 3 / 2 3 / 2 f n n T n n a b f n n n = Θ = Θ = = = = = 例 T(n) = 3T(n / 4) + nlog n ( ) ( log ) 3/ 4, ( / ) 3( / 4)log( / 4) (3/ 4) log ( ), ( ) ( ), 0.2, 3, 4, ( ) log , ( ), 3 4 log log4 3 0.793 T n n n c n af n b n n n n cf n f n n a b f n n n n O n = Θ = = ≤ = = Ω ≈ = = = = + 充分大 ε ε 59 计算一个数的幂 60