算法设计与分析-第6章分治.ppt

1、算法设计与分析,分治法,分治法,主要内容： 介绍分治法的基本思想和分治算法的设计与分析 。,分治法,一.分治法的基本思想 几个典型例子： 二分查找（二分搜索） 快速排序 二叉树遍历 观察：上述问题的算法有什么共同特点?,分治法,一.分治法的基本思想 1基本思想 将原问题分解成若干个相互独立的与原问题性质相同的子问题，用同样的方法解这些子问题并将这些子问题的解组合起来得到原问题的解。 说明：子问题还用相同的分治方法解，分治过程一直进行下去，直至子问题的规模充分小，可直接解为止。,分治法,一.分治法的基本思想 分治法图示：,原问题P,子问题P1,子问题P2,子问题Pk,P1的解,P2的解,Pk的解

2、,原问题P的解,组合,直接解或分治法解,分解,分治法,一.分治法的基本思想 2分治算法的一般形式 分治算法的一般步骤： 分解 直接或递归求解子问题 组合 由于分治法本身的递归特性，一般用递归实现分治算法。 递归分治算法的一般形式 过程 divideandconquer ( P ) 例子：求n (n=2k, k=1)个整数的最大值和最小值。(例子),分治法,一.分治法的基本思想 3分治算法的时间复杂性分析 递归方程 分治算法的时间复杂性C(n)往往满足如下的递归方程：,其中，n: 问题的规模。 n0: 可直接解的问题规模的阈值。 a: 分解出的需要求解的子问题的个数。 n/c: 分解出的子问题的

3、规模。 g(n): 分解规模为n的问题以及组合相应子问题的解 所需的时间。 d: 直接解规模为n0的问题所需的时间。,分治法,一.分治法的基本思想 3分治算法的时间复杂性分析 递归方程的求解：（第2章） 尽量利用公式,分治法,二.分治算法的设计与分析 1. 归并排序（合并排序） （6.3 P105） 基本思想： /对序列a1, a2, an归并排序 if n1 then 将a1, a2, an分解成a1, a2,an/2 和an/2+1,an/2+2, an 两个子序列；/分解 分别对两个子序列归并排序； /递归 将两个有序子序列合并成一个有序序列; /组合 end if,分治法,二.分治算法

4、的设计与分析 1. 归并排序（合并排序） （6.3 P105） 归并排序过程图示 (P106 图6.1) 归并排序过程 递归的归并排序算法 算法6.3 MERGESORT 迭代的算法： （ 算法1.6 BOTTOMUPSORT P10）,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历； 3先右（子树）后左（子树）的遍历。,二、先左

5、后右的遍历算法,先序（根）的遍历算法,中序（根）的遍历算法,后序（根）的遍历算法,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后序（根）的遍历算法：,课堂提问：,有以下结构的二叉树 写出其先序、中序和后序遍历的序列,分治法,二.分治算法的设计与分析 2. 大整数乘法 （6.7 P118） 问题：设u, v为两个n位二进制整数，要求uv 的值。 传统算法： 需(n2)次一位数乘法和(n2)次一位数加法。 分治算法： 不妨设n=2k, 则 u=w2n/2+x v=y2n/2+z 于是 uv=wy2n+(wz+xy) 2n/2+xz,分治法,

6、二.分治算法的设计与分析 2. 大整数乘法 （6.7 P118） 求两个n 位数的乘积uv问题可分解为求4个n/2位数乘积子问题：wy, wz, xy, xz。 解的组合通过2n次一位数的加法和(3/2)n次位移实现。 该分治算法的时间复杂性T(n)满足： T(n)=1 , n=1 T(n)=4T(n/2)+bn , n1 解得： T(n)= ( )= (n2)。,分治法,二.分治算法的设计与分析 2. 大整数乘法 （6.7 P118） 算法的改进： wz+xy=(w+x)(y+z)-wy-xz 于是 uv=wy2n+(w+x)(y+z)-wy-xz) 2n/2+xz 求两个n 位数的乘积uv

7、问题可分解为求3个n/2位数乘积子问题：wy, (w+x)(y+z), xz。 问题的分解和解的组合通过4n次一位数的加法和(3/2)n次位移实现。,分治法,二.分治算法的设计与分析 2. 大整数乘法 （6.7 P118） 改进的分治算法的时间复杂性T(n)满足： T(n)=1 , n=1 T(n)=3T(n/2)+bn , n1 解得： T(n)= ( ) (n1.59)。,分治法,二.分治算法的设计与分析 3. 矩阵乘法 (6.8 P119) 问题描述：设A , B为n阶方阵，要求C=AB。 传统算法： 求C=AB需要n3次乘法运算和n3-n2次加法运算，时间复杂性为(n3)。 分治算法（

8、分治算法）：不妨设n=2k。 (1) 简单的递归方法 (2) STRASSEN算法,例 一 两 个 矩 阵 相 乘,void mult(int a, int b, int /for /mult,基本操作: 乘法操作,时间复杂度: O(n3),分治法,二.分治算法的设计与分析 4. 循环赛日程表 问题描述：设有n（n=2k）个选手进行网球循环赛，要设计一个满足以下条件的比赛日程表： (1) 每个选手必须与其他n-1个选手各赛一次； (2) 每个选手一天只能赛一次； (3) 循环赛一共进行n-1天。,问题的抽象（问题的抽象）,分治算法（分治算法）,分治法,二.分治算法的设计与分析 5. 快速排序

9、基本思想： /将A1.n中的元素按升序快速排序。 if n1 then 将A1.n中元素进行划分，使得对于某w, A1.w-1中元素=Aw； 将A1.w-1中的元素按升序快速排序; 将Aw+1.n中的元素按升序快速排序; end if,分治法,二.分治算法的设计与分析 5. 快速排序 划分算法：(P113) 快速排序算法：（P114）,分治法,二.分治算法的设计与分析 6. 寻找第k小元素（选择问题）（6.5 P109） 问题描述：给出一个n个元素的序列，求其中的第k小元素（即序列按升序排序后的第k个元素）。 中项（中间元素）: 一个序列的中项为该序列的第 小元素。,分治法,二.分治算法的设计

10、与分析 6. 寻找第k小元素（选择问题）（6.5 P109） 有关算法： 通过排序可求序列的第k小元素，需要(nlogn)时间。 利用随机快速排序的思想，平均情况下时间复杂性可达(n)（第14章）。,分治法,二.分治算法的设计与分析 6. 寻找第k小元素（选择问题）（6.5 P109） 线性时间选择算法： 基本思想：若分治算法中，每次分解子问题后，只取其中一个子问题解之，丢弃其余的子问题。每次递归调用，问题的规模以常数因子被减小。设分解问题只需线性时间，则算法的时间复杂性满足： T(n)=T(sn)+cn , nn0 T(n)= (1) , n=n0 （s1） 解得：T(n)=cn(sk-1+ sk-2+s+1)+ (1)= (n) (设nsk=n0),分治法,二.分治算法的设计与分析 6. 寻找第k小元素（选择问题）（6.5 P109） 线性时间选择算法： 算法：算法6.4 SELECT 时间复杂性： 时间复杂性分析,分治法,二.分治算法的设计与分析 7. 最近点对问题 ( 6.9 P121 ) 问题描述：设S是平面上n个点的集合，求S中距离最近的点对（的距离）。 蛮力算法：求出S中所有n(n-1)/2个点对的距离。时间复杂性为(n2)。