**********************算法设计与分析福建师范大学算法设计与分析福建师范大学算法设计与分析福建师范大学算法设计与分析——分治法分治法主要内容：介绍分治法的基本思想和分治算法的设计与分析。分治法一.分治法的基本思想几个典型例子：二分查找（二分搜索），快速排序，二叉树遍历观察：上述问题的算法有什么共同特点?1．基本思想将原问题分解成若干个相互独立的与原问题性质相同的子问题，用同样的方法解这些子问题并将这些子问题的解组合起来得到原问题的解。说明：子问题还用相同的分治方法解，分治过程一直进行下去，直至子问题的规模充分小，可直接解为止。分治法一.分治法的基本思想分治法图示：原问题P子问题P1子问题P2子问题PkP1的解P2的解Pk的解原问题P的解组合直接解或分治法解分解…………分治法一.分治法的基本思想2．分治算法的一般形式分治算法的一般步骤：分解→直接或递归求解子问题→组合由于分治法本身的递归特性，一般用递归实现分治算法。递归分治算法的一般形式过程divideandconquer(P)例子：求n(n=2k,k=1)个整数的最大值和最小值。（例子）递归分治算法与一般的递归算法分治法一.分治法的基本思想3．分治算法的时间复杂性分析递归方程分治算法的时间复杂性C(n)往往满足如下的递归方程：其中，n:问题的规模。n0:可直接解的问题规模的阈值。a:分解出的需要求解的子问题的个数。n/c:分解出的子问题的规模。g(n):分解规模为n的问题以及组合相应子问题的解所需的时间。d:直接解规模为n0的问题所需的时间。 分治法一.分治法的基本思想3．分治算法的时间复杂性分析递归方程的求解：（第2章）尽量利用公式分治法二.分治算法的设计与分析1.归并排序（合并排序）（6.3P105）基本思想：//对序列a1,a2,…,an归并排序ifn1then将a1,a2,…,an分解成a1,a2,…,an/2和an/2+1,an/2+2…,an两个子序列；//分解分别对两个子序列归并排序；//递归将两个有序子序列合并成一个有序序列;//组合endif分治法二.分治算法的设计与分析1.归并排序（合并排序）（6.3P105）归并排序过程图示递归的归并排序算法算法6.3MERGESORT迭代的算法：（算法1.6BOTTOMUPSORTP10）分治法二.分治算法的设计与分析2.大整数乘法（6.7P118）问题：设u,v为两个n位二进制整数，要求uv的值。传统算法：需Θ(n2)次一位数乘法和Θ(n2)次一位数加法。分治算法：不妨设n=2k,则u=w2n/2+xv=y2n/2+z于是uv=wy2n+(wz+xy)2n/2+xz分治法二.分治算法的设计与分析2.大整数乘法（6.7P118）求两个n位数的乘积uv问题可分解为求4个n/2位数乘积子问题：wy,wz,xy,xz。解的组合通过3次加法和(3/2)n次位移实现。该分治算法的时间复杂性T(n)满足：T(n)=1,n=1T(n)=4T(n/2)+bn,n1解得：T(n)=Θ()=Θ(n2)。分治法二.分治算法的设计与分析2.大整数乘法（6.7P118）算法的改进：wz+xy=(w+x)(y+z)-wy-xz于是uv=wy2n+((w+x)(y+z)-wy-xz)2n/2+xz