算法设计与分析第三章 分治法

North China Electric Power University
分治的具体过程： 分治的具体过程：
if 问题规模小到可以直接解决 直接解决该问题 else 将问题分解成ｋ 将问题分解成ｋ个规模较小的子问题 for(i=1;i<=k;i++) 递归调用该分治算法， 递归调用该分治算法，分别解决每一个子问题 将各子问题的解合并为原问题的解
T(n-1) n-2 …… T(1) 0
North China Electric Power University
分治-归并排序算法是用分治策略实现对 个元素进行排序的算法 分治 归并排序算法是用分治策略实现对n个元素进行排序的算法。 归并排序算法是用分治策略实现对 个元素进行排序的算法。 基本思想： 时终止排序， 基本思想：当n=1时终止排序，否则将待排序元素分成大小大致 时终止排序 相同的两个子集，分别对两个子集进行排序， 相同的两个子集，分别对两个子集进行排序，最终将排序好的 子集合并成为所要求的排序好的集合。 子集合并成为所要求的排序好的集合。 template <class Type> void Msort(Type r[],Type r1[],int s,int t); { if (s=t) r1[s] = r[s] else { m = (s+t)/2; //将r[s..t]平分为 平分为r[s..m]和r[m+1..t] 将 平分为 和 Msort (r, r1, s, m); Msort (r, r1, m+1, t); Merge (r, r1, s, m, t); Copy(r1,r,s,t); } } template <class Type> void Merge_sort (Type r[],Type r1[],int n) { MSort(r, r1, 1, n); // 对记录序列 对记录序列r[1..t]作2-路归并排序 } 作
North China Electric Power University
第三章 分治法
★ ★ ★ ★ ★
分治法的基本思想 二分搜索技术 合并排序 大整数乘法 Strassen矩阵乘法 矩阵乘法 矩阵
★ 第K小元素问题
North China Electric Power University
§1 分治法的基本思想
North China Electric Power University
T(n)
n
n
T(n/2)
n/2
T(n/2)
n/2
n
T(n/2) n/2
T(n/2) n/2
T(n/2) n/2
T(n/2) n/2
n Biblioteka Baidu ……
Θ(nlog n)
North China Electric Power University
X11 X12
X15:X16
X15 X16
North China Electric Power University
§2 二分搜索技术
问题描述：给定已排序好的 个元素 个元素a[1:n],现在要在这 个元素 现在要在这n个元素 问题描述：给定已排序好的n个元素 现在要在这 中找出一特定元素x。 中找出一特定元素 。 二分搜索法的基本思想： 个元素分成大致相同的两半， 二分搜索法的基本思想：将n个元素分成大致相同的两半，取 个元素分成大致相同的两半 a[n/2]与x做比较，如果 做比较， 与 做比较 如果x=a[n/2]则，则找到 ，算法终止；如果 则 则找到x，算法终止； x≤a[n/2]，则只要在 的左半部继续搜索；如果 的左半部继续搜索； ，则只要在a的左半部继续搜索 如果x>a[n/2]，则 ， 只要在a的右半部继续搜索 的右半部继续搜索。 只要在 的右半部继续搜索。 template <class Type> int Binary_Search(Type a[],int left ,int right,const Type &x) { if (left>right) return(-1); else { m=(left+right)/2; if (x==a[m]) then return(m) ; else if ( x>a[m]) return(Binary_Search(a,m+1,right,x)); else return(Binary_Search(a,left,m-1,x)); } }
X1-8:X9-16 X1-4:X5-8 X1-2:X3-4 X1:X2
X1 X2
X9-12:X13-16 X5-6:X7-8 X9-10:X11-12 X9:X10
X9 X10
X13-14:X15-16 X13:X14
X13 X14
X3:X4
X3 X4
X5:X6
X5 X6
X7:X8
X7 X8
X11:X12
North China Electric Power University
template <class Type> void Merge(Type r[],Type r1[],int s,int m,int t) { i=s; k=s; j=m+1; while ((i<=m) && (j<=t)) { if (r[i] <=r[j]) {[r1[k]=r[i]; i=i+1;} else { r1[k]=r[j]; j=j+1;} k=k+1; } if (i>m) Copy(r,j,t,r1); else Copy(r,i,m,r1); } Merge和Copy可以在 可以在O(n)时间内完成，因此分治归并排序算法 时间内完成， 和 可以在 时间内完成 所需的时间T(n)满足： 满足： 所需的时间 满足 O(1) n =2 T(n)= 2T(n/2)+O(n) n >2 2 解此递归方程可得T(n)=O(nlogn) 解此递归方程可得
North China Electric Power University
计算机算法设计与分析
Computer Algorithms Design & Analysis
华北电力大学计算机科学与工程系
Dept. of Computer Science&Engineering of North China Electric Power University
分治法与软件设计的模块化方法非常相似。 分治法与软件设计的模块化方法非常相似。为了解决一个 大的问题，可以： 把它分成两个或多个更小的问题； 大的问题，可以： 1) 把它分成两个或多个更小的问题； 2) 分 别解决每个小问题； 3) 把各小问题的解答组合起来，即可得到 别解决每个小问题； 把各小问题的解答组合起来， 原问题的解答。小问题通常与原问题相似， 原问题的解答。小问题通常与原问题相似，可以递归地使用分 而治之策略来解决。 而治之策略来解决。
分治法所能解决的问题一般具有以下几个特征(适用条件) 分治法所能解决的问题一般具有以下几个特征(适用条件)
1. 该问题的规模缩小到一定的程度就可以容易地解决； 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题； 2. 该问题可以分解为若干个规模较小的相同问题；即该问题具 有最优子结构性质； 有最优子结构性质； 利用该问题分解出的子问题的解可以合并为该问题的解； 3. 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的， 4. 该问题所分解出的各个子问题是相互独立的，即子问题之间 不包含公共的子问题。 不包含公共的子问题。
North China Electric Power University
一般的算法设计模式如下： 一般的算法设计模式如下： Divide_and_Conquer（P） Divide_and_Conquer（ if |P|≤n0 return（ADHOC（ then return（ADHOC（P）） 分解为较小的子问题P1 P2、...、 P1、 将P分解为较小的子问题P1、P2、...、Pk for i←1 to k do Divide_and_Conquer（Pi） 递归解决Pi yi ← Divide_and_Conquer（Pi） △ 递归解决Pi MERGE（y1，y2，...，yk） T ← MERGE（y1，y2，...，yk） △ 合并子问题 Return（ Return（T） 根据分治法的分割原则，原问题应该分为多少个子问 根据分治法的分割原则， 题才较适宜？各个子问题的规模应该怎样才为适当？ 题才较适宜？各个子问题的规模应该怎样才为适当？这 些问题很难予以肯定的回答。但人们从大量实践中发现， 些问题很难予以肯定的回答。但人们从大量实践中发现， 在用分治法设计算法时，最好使子问题的规模大致相同。 在用分治法设计算法时，最好使子问题的规模大致相同。 换句话说，将一个问题分成大小相等的k 换句话说，将一个问题分成大小相等的k个子问题的处理 方法是行之有效的。 方法是行之有效的。
North China Electric Power University
分治§3 分治-归并排序
问题： 个元素的排序问题 即将n个元素按一定规则排列成一 个元素的排序问题， 问题：n个元素的排序问题，即将 个元素按一定规则排列成一 个有序序列。 个有序序列。 简单选择排序的思想：将这 个元素存储在一个数组中 个元素存储在一个数组中， 简单选择排序的思想：将这n个元素存储在一个数组中，首先 通过n-1次比较找出这个数组中的最小元素 次比较找出这个数组中的最小元素， 通过 次比较找出这个数组中的最小元素，并将这个元素与 数组中的第一个交换。 数组中的第一个交换。如果挑选出的元素恰好占交换后应占 的元素位置，则交换不必进行。 次在剩余的 次在剩余的n-i+1个元素中 的元素位置，则交换不必进行。第i次在剩余的 个元素中 找出最小元素与第i个元素交换。重复这一步骤，直到i=n-1。 找出最小元素与第 个元素交换。重复这一步骤，直到 。 个元素交换 其时间复杂性为： 其时间复杂性为： T(n)=T(n-1)+n-1 T(n) n-1 T(n)=n-1+n-2+…+2+1+0 =n(n-1)/2
North China Electric Power University
分治策略算法的复杂度分析 T(n)=af(n/b)+d(n) 他的复杂度分析采用递归算法提到的Master Master定理 他的复杂度分析采用递归算法提到的Master定理
伪币问题]： 例 [伪币问题 ： 伪币问题 给你一个装有1 个硬币的袋子 个硬币的袋子。 个硬币中有一个是伪 给你一个装有 6个硬币的袋子。1 6个硬币中有一个是伪 造的，并且那个伪造的硬币比真的硬币要轻一些。 造的，并且那个伪造的硬币比真的硬币要轻一些。给你一台 没有砝码的天平，试用较少的测量次数找出这个伪币。 没有砝码的天平，试用较少的测量次数找出这个伪币。
North China Electric Power University
设在n个元素的数组中查找 需要的比较次数为 设在 个元素的数组中查找x需要的比较次数为 个元素的数组中查找 需要的比较次数为T(n)，如果每 ， 次比较x和 根本不在L中 次比较 和a[m]时，总有 时 总有x<>a[m]，即x根本不在 中，则： ， 根本不在 T(n)=2+T(n/2),T(1)=1 该方程的解为T(n)=O(logn)。 该方程的解为 。 所以在最坏情况下二分查找法的复杂度为O(logn)。 所以在最坏情况下二分查找法的复杂度为 。 T(n) T(n/2) …… T(1) 2 2 2 2 2 …… 2 2log n= Θ(log n)
金块问题] 例：[金块问题 金块问题 老板有一袋金块(共 块 的幂（ 老板有一袋金块 共n块，n是2的幂（n>=2）)，将有两名 是 的幂 ）， 最优秀的雇员每人得到其中的一块， 最优秀的雇员每人得到其中的一块，排名第一的得到最重的 那块，排名第二的雇员得到袋子中最轻的金块。 那块，排名第二的雇员得到袋子中最轻的金块。假设有一台 比较重量的仪器， 比较重量的仪器，我们希望用最少的比较次数找出最重的金 块。 也就是这样一个问题,同时求 个数中的最大值和最小值 也就是这样一个问题 同时求n个数中的最大值和最小值， 同时求 个数中的最大值和最小值， n为2的整数次幂。 的整数次幂。 为 的整数次幂