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

第10章 组合分析初步 10.1 加法法则和乘法法则10.2 基本排列组合的计数方法10.3 递推方程的求解与应用二分归并排序n二分归并排序的主要思想n将被排序的数组划分成相等的两个子数组，将被排序的数组划分成相等的两个子数组，n然后递归使用同样的算法分别对两个子数组然后递归使用同样的算法分别对两个子数组 n最后将两个排好序的子数组归并成一个数组。最后将两个排好序的子数组归并成一个数组。n二分归并排序算法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)归并归并二分归并排序算法n19,14,11,18,30,17,6,20n19,14,11,18,30,17,6,20n19,14,11,18,30,17,6,20n19,14,11,18,30,17,6,20n14,19,11,18,17,30,6,20n11,14,18,19,6,17,20,30n6,11,14,17,18,19,20,30二分归并排序算法n设要比较的数组元素个数为n=2k，nW(n)表示该算法在最坏情况下所做的比较次数，表示该算法在最坏情况下所做的比较次数，n将n个数组元素分为两个子数组A和B(大小相等)，n排序数组排序数组A或或B的工作量分别为的工作量分别为W(n/2)。n因为数组因为数组A和和B总共有总共有n个元素，归并它们至多需要个元素，归并它们至多需要n-1次比较，次比较，n因此，对n个数进行二分归并排最坏情况下的比较次数満足如下递推方程：W(n)=2W(n/2)+n-1,n=2kW(1)=0分而治之算法的特点n符号设定：na,b 为正整数，为正整数，n为问题的输入规模，为问题的输入规模，nn/b为子问题的输入规模，为子问题的输入规模，na为子问题的个数，为子问题的个数，nd(n)为将原问题分解成子问题以及将子问题的解综合得为将原问题分解成子问题以及将子问题的解综合得到原问题解的代价。到原问题解的代价。n一般情况下有：T(n)=aT(n/b)+d(n),n=bkT(1)=1n如对n个正整数进行二分归并排序nb=2,a=2,d(n)=n-1W(n)=2W(n/2)+n-1,n=2kW(1)=0分而治之算法的迭代过程T(n)=aT(n/b)+d(n),=aaT(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 分而治之算法的结果形式n当当d(n)=c时，时，c为某个常数，代入上式得为某个常数，代入上式得分而治之算法的结果的应用n如已知递推方程：如已知递推方程：T(n)=4T(n/2)+O(n)n由由T(n)=aT(n/b)+d(n),n=bkn则：b=2,a=4,d(n)=O(n)，代入下式得，代入下式得