《算法设计与分析基础第2版清华出版社ch4分治法-02讲义教材》由会员分享，可在线阅读，更多相关《算法设计与分析基础第2版清华出版社ch4分治法-02讲义教材（47页珍藏版）》请在金锄头文库上搜索。
1、第4章 分治法,分治法的基本思想 将规模为N的问题分解为k个规模较小的子问题,使这些子问题相互独立可分别求解,再将k个子问题的解合并成原问题的解.如子问题的规模仍很大,则反复分解直到问题小到可直接求解为止。 在分治法中,子问题的解法通常与原问题相同,自然导致递归过程。,分治法是按照以下方案工作的： 1. 将问题的实例划分为同一个问题的几个较小的实例，最好拥有同样的规模。 2.对这些较小实例的求解（一般使用递归方法，但在问题规模足够小的时候，有时也会使用一些其他方法）。 3.如果必要的话，合并这些较小问题的解，以得到原始问题的解。,原始问题的规模是n,子问题1的规模是n/2,子问题2的规模是n/
2、2,主定理 如果在递推式中f(n)(n)，其中d=0,那么： （n） 当a b时 （对O和符号来说类似的结论也是成立的）,例如，对于上面的分治法求和算法，当输入规模为n=2时，加法运算次数A(n)可以用下面的例子来说，a=1, b=2, d=0；这样一来，因为a b, A(n) n）=（n）=（n）,本章主要内容： 4.1 合并排序 4.2 快速排序 4.3 折半排序 4.4 二叉树遍历及其相关特性 4.5 大整数乘法和矩阵相乘 4.6 解最近对问题与凸包问题,4.1 合并排序,问题： 将n个元素排成非递减顺序。,算法思路： 若n为1,算法终止;否则,将n个待排元素分割成k(k=2)个大致相等
3、子集合A、B,对每一个子集合分别递归排序,再将排好序的子集归并为一个集合。,合并排序的递归算法,算法 MergeSort(A0.n-1 ) / 输入：未排序序列A0.n-1 / 输出：已排序序列A0.n-1 if n 1 copy A0.n/2-1 to B0.n/2-1 copy An/2.n-1 to C0.n/2-1 MergeSort( B ) MergeSort( C ) Merge( B,C,A ) 其中，Merge(B,C,A)是将有序数组B、C合并为有序数组A的算法。,算法 Merge(B0.p-1,C0.q-1,A0.p+q-1) i0,j0,k0; while ip and
4、 jq do if BiCj AkBi, ii+1 else AkCj, jj+1 kk+1 if i=p copy Ci.q-1 to Ak.p+q-1 else copy B0.p-1 to A0.p+q-1,合并排序举例,注：合并 2,3,8,9 与1,4,5,7 的过程： 从两个序列的头部开始合并：2与1比较，1被移到结果序列；2与4比较，2被移入结果序列；4与3比较，3被放入结果序列；4和8比较，4被放入结果序列, 8和5比较.， 合并排序的后半部分是”归并排序“。,归并排序举例： 初始序列 a 8 3 2 9 7 1 5 4 归并到b 3 8 2 9 1 7 4 5 复制到a 3
5、8 2 9 1 7 4 5 归并到b 2 3 8 9 1 4 5 7 复制到a 2 3 8 9 1 4 5 7 归并到b 1 2 3 4 5 7 8 9 复制到a 1 2 3 4 5 7 8 9,二路归并,注：归并 2，3，8，9 与1，4，5，7 的过程： 从两个序列的头部开始归并：2与1比较，1被移到结果序列；4与2比较，2被移入结果序列；4与3比较，3被放入结果序列；4和8比较，4被放入结果序列, 8和7比较.，,合并排序的效率分析,设n=2k, 则关键字比较次数的递推关系式为： C(n)=2C(n/2)+Cmerge(n) (n1) C(1)=0 在最坏情况下，归并排序的效率Cmerg
6、e(n)=n-1, 于是，在最坏情况下 C (n)=2C(n/2)+n-1 解得 C(n)=nlog2n-n+1(nlog2n),4.2 快速排序,算法思路: 对于输入A0. n-1，按以下三个步骤进行排序： (1)分区:取A中的一个元素为支点(pivot) 将A0.n-1划分成3段: A0.s-1, As , As+1.n-1, 使得 A0.s-1中任一元素As, As+1.n-1中任一元素 As; 下标s 在划分过程中确定。 (2)递归求解:递归调用快速排序法分别对A0.s-1和As+1.n-1排序。 (3)合并:合并A0.s-1, As, As+1.n-1为A0.n-1,快速排序算法 Q
7、uickSort(Al.r) / 使用快速排序法对序列或者子序列排序 / 输入：子序列Al.r或者序列本身A0.n-1 / 输出：非递减序列A if l r s Partition( Al.r ) QuickSort( Al.s-1 ) QuickSort( As+1.r ) /s是中轴元素/基准点，是数组分区位置的标志 中轴元素如何选？,数组的分区算法：,算法 Partition( Al.r ) / 输入：子数组Al.r / 输出：分裂点/基准点pivot的位置 p Ali l; j r+1 repeat repeati i + 1until Ai p repeat j j 1 until
8、Aj p swap( Ai, Aj ) until i j swap( Ai, Aj ) swap( Al, Aj ) return j,分区算法,该算法中使用了两次扫描数组的高效方法： 指针i从数组左边开始扫描，忽略小于中轴的元素，遇到大于等于中轴的元素Ai时停止，指针j从数组右边开始扫描，忽略大于中轴的元素，遇到小于等于中轴的元素Aj时停止，然后交换AiAj。指针不相交则继续。,快速排序的例子（双向扫描）,例如：n=8 初始数组 A0.n-1=8, 4, 1, 7, 11, 5, 6, 9, 取元素A0=8作为分裂点, 位置： 0 1 2 3 4 5 6 7 8, 4, 1, 7, 11,
9、 5, 6, 9 指针i、j分别向中间移动 8, 4, 1, 7, 11, 5, 6, 9 指针停止时，交换 8, 4, 1, 7, 6, 5, 11, 9 ,快速排序的例子,合并: 把A0.s-1中的元素放在分裂点元素8之前, As+1.n-1中的元素放在分裂点元素之后, 结果1, 4, 5, 6, 7, 8, 9, 11,排序: A0.s-1=1, 4, 5, 6, 7; A s+1.n-1=9, 11。,分解得： A0.s-1=4, 1, 7, 6, 5; As=8; As+1.7=11,9; s=5,快速排序效率分析,基本操作：比较 最坏情况下： 在进行了n+1次比较后建立了分区，还会
10、对数组进行排序，继续到最后一个子数组An-2.n-1。总比较次数为： C(n)=(n+1)+n+3 =(n+2)(n+1)/2-3 (n2),4.3 折半查找,原理：扫描整个列表，找出最小元素，然后将最小元素与第一个元素交换位置。从第二个元素开始扫描列表，找出n-1个元素中的最小元素，将最小元素与第二个元素交换位置，如此类推，做n-1遍后排序结束。 算法伪代码：SelectionSort(A0.n-1) for i=0 to n-2 do min=i for j=i+1 to n-1 do if AjAmin min=j swap Ai and Amin,BinarySearch( A0.n-
11、1, k ) / 输入：已排序大小为n的序列A，待搜索对象k / 输出：如果搜索成功，则返回k的位置，否则返回-1 l=0,r=n-1; While lr mid= (l+r)/2 if k = Amid return mid else if k Amid r=m-1 else l=m+1 return -1,折半查找伪代码,折半查找效率分析： 基本操作：比较 最坏情况下，比较次数 C(n)=C( n/2)+1 C(1)=1 设n= ，可解得 C(n)=k+1=log2n+1 于是 C(n)(log2n),折半查找举例：,位置：0 1 2 3 4 5 6 7 8 9 10 11 12 值： 3
12、,14,27,31,39,42,55,70,74,81,85,93,98 K=70 迭代1 l=0 m=6 r=12 迭代2 l m=9 r 迭代3 l r 结果 m= (7+8)/2=7,4.4 二叉树遍历及其相关特性,所谓二叉树的遍历指的是遵循某一种次序来访问二叉树上的所有结点，使得树中每一个结点被访问了一次且只访问一次。 由于二叉树是一种非线性结构，树中的结点可能有不止一个的直接后继结点，所以遍历以前必须先规定访问的次序。,本节作业,思考题：习题4.1-8, 4.2-5, 4.3-4, 4.3-10 作业：习题4.1-5，4.2-1, 4.3-1,中序遍历（Inorder Travers
13、al）,二叉树的中序遍历算法比较简单，使用递归的策略。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则中序遍历的算法步骤如下： （1）对左子树L执行中序遍历算法 （2）访问输出根结点V的值。 （3）对右子树R执行中序遍历算法。,前序遍历（Preorder Traversal）,有了上面的中序遍历的过程，前序遍历也是类似的。在遍历以前首先确定遍历的树是否为空，如果为空，则直接返回；否则前序遍历的算法步骤如下： （1）访问输出根结点V的值； （2）对左子树L执行前序遍历算法。 （3）对右子树R执行前序遍历算法。,前序遍历执行过程图,二叉树的构造,二叉树的高度计算,算法 Height(
14、T) /输入一棵二叉树T /输出二叉树的高度 /二叉树高度定义：叶子到树根的最长路径 if T= return -1 else return maxHeight(L), Height(R)+1 例：计算上例中二叉树的高度 H(T)=1+maxH(2),H(6)=2+maxH(3),H(4) =3+H(5)=5,4.5 大整数乘法和Strassen矩阵乘法,设A、B为两个n位的大整数，直接计算需要执行n2次1位数的乘法。 A=a110n/2+a2 ，B=b110n/2+b2 直接计算： AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a
15、2b2 递归公式为： C(n)=4C(n/2)+kn C(1)=1 解得 C(n) O(n2),改进的乘法,AB=(a110n/2+a2)(b110n/2+b2) =a1b110n+(a1b2+a2b1)10n/2+a2b2 =a1b110n+(a1+a2)(b1+b2)-a1b1-a2b2)10n/2+a2b2 验证： (a1+a2)(b1+b2)-a1b1-a2b2)=(a1b2+a2b1) 这种方法需要3次n/2位的乘法及一些加减法。 记C(n)为计算两个n位整数相乘所需的基本操作执行次数，则,有 C(n)=3C(n/2)+kn C(1)=1 其中，k为常数。 解此递归方程，得 C(n)=nlog3+2knlog3-2kn O(nlog3) O(n1.58) 可见，乘法效率有改善。,2、 Strassen矩阵乘法,矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。若A和B是2个nn的矩
