10-3 组合分析 离散数学 教学课件.pptVIP

第10章 组合分析初步 10.1 加法法则和乘法法则 10.2 基本排列组合的计数方法 10.3 递推方程的求解与应用 二分归并排序 二分归并排序的主要思想 将被排序的数组划分成相等的两个子数组， 然后递归使用同样的算法分别对两个子数组 最后将两个排好序的子数组归并成一个数组。 二分归并排序算法 Mergesort (A, p, r) //对数组A的下标p到r之间的数排序 if (pr) q = [(p+r)/2]; Mergesort (A, p, q); Mergesort (A, q+1,r); Merge (A,p,q,r); //把排好序的数组A(p,q)与A(q+1,r)归并 二分归并排序算法 [19, 14, 11, 18, 30, 17, 6, 20] [19, 14, 11, 18] , [30, 17, 6, 20] [19, 14] ,[11, 18], [30, 17], [6, 20] [19], [14], [11], [18], [30], [17], [6], [20] [14, 19] ,[11, 18], [17, 30], [6, 20] [11, 14, 18, 19] , [6, 17, 20, 30] [6, 11, 14, 17, 18, 19, 20, 30] 二分归并排序算法 设要比较的数组元素个数为n=2k， W(n)表示该算法在最坏情况下所做的比较次数， 将n个数组元素分为两个子数组A和B(大小相等)， 排序数组A或B的工作量分别为W(n/2)。 因为数组A和B总共有n个元素，归并它们至多需要n-1次比较， 因此，对n个数进行二分归并排最坏情况下的比较次数満足如下递推方程： W (n) = 2W (n/2) + n-1, n=2k W (1) = 0 递推方程的实例——算法分析 哪种排序算法在最坏情况下复杂度比较低？ 插入排序 W(n) = W(n ?1) + n ?1 W(1) = 0 解得 W(n) = O(n2). 归并排序 不妨设 n = 2k W(n) = 2W(n/2) + n－1 W(1) = 0 解得 W(n) = O(nlogn) 分而治之算法的特点 符号设定： a, b 为正整数，n为问题的输入规模， n/b为子问题的输入规模， a为子问题的个数， d(n)为将原问题分解成子问题以及将子问题的解综合得到原问题解的代价。 一般情况下有： T (n) = aT (n/b) + d(n), n=bk T (1) = 1 如对n个正整数进行二分归并排序 b = 2, a = 2, d(n) = n-1 W (n) = 2W (n/2) + n-1, n=2k W (1) = 0 分而治之算法的迭代过程 T (n) = aT (n/b) + d(n), = a[aT (n/b2) + d(n/b)] + d(n) = a2T (n/b2) + ad(n/b) + d(n) = …… =akT (n/bk) + ak-1d (n/bk-1) + ak-2d (n/bk-2) + …+ ad(n/b) + d(n) 其中， T (n/b) = aT (n/b/b) + d(n/b ) T (1) = 1, n = bk 分而治之算法的结果形式 当d(n)=c时，c为某个常数，代入上式得 分而治之算法的结果形式 当d(n)=cn时，c为某个常数，代入上式得 如二分归并排序： b=2, a=2, d(n)=n-1=O(n) 代入公式，其中a=b ，得 W(n)=O(nlogn) 分而治之算法的结果的应用 如已知递推方程：T(n)=4T(n/2)+O(n) 由T (n) = aT (n/b) + d(n), n=bk 则：b=2, a=4, d(n)=O(n)，代入下式得 * 如A=[1, 4, 7, 10], B=[2, 6, 8, 20]， 则此情况下比较次数达到最大，为4×2-1=7次 * 如A=[1, 4, 7, 10], B=[2, 6, 8, 20]， 则此情况下比较次数达到最大，为4×2-1=7次