算法分析与设计分治法概要PPT学习教案

1、会计学1算法分析与设计分治法概要算法分析与设计分治法概要2008-09-01分治策略基本思想 当问题的规模较大而无法直接求解时，将整个问题分成若干个小问题，然后分而治之。 可用递归过程描述。一般情况下，子问题与原始问题“同质”第1页/共37页2008-09-01问题P的规模阈值基本子算法，解小规模问题分解求解子问题合并子问题k通常为2第2页/共37页2008-09-01nk=2: 二分是最常用的分解策略；nSMALL(p,q)：布尔函数，判断输入规模q-p+1是否足够小而无需再进一步分就可求解；nG(p,q)： 当SMALL(p,q)为真时，对输入规模为q-p+1的子问题求解；nDIVIDE(

2、p.q)：当规模q-p+1还较大时，对规模为q-p+1的子问题进一步分解，返回值为p,q区间进一步的分割;nCOMBINE(x,y)：子结果的合并函数，将区间p,m和m+1,q上的子问题的解合并成区间p,q上的“较完整”的解。n当p=1,q=n时，就得到整个问题的解。第3页/共37页2008-09-01二叉树的前序遍历沿左子树递归沿右子树递归子问题的解处理完左子树处理完右子树，和并两个分支的解处理右子树第4页/共37页2008-09-011)()/(1) 1 ()(nnfmnkTnOnT合并k个子问题的时间子问题需要的时间基本问题需常数时间渐近时间表示mknOmknnOmknOnTkm),()

3、,log(),()(log第5页/共37页2008-09-01否则足够小)()2/(2) 1 ()(nfnTnOnT渐近时间表示)log()(nnOnT第6页/共37页2008-09-01第7页/共37页2008-09-01第8页/共37页2008-09-01注： 给定一个按非降次序排列的元素数组a1:n，n1,判断x是否出现。若是，置j，使得x=aj若非，j=0第9页/共37页2008-09-01例例：假定a1:9中顺序存放着以下9个元素：-15，-6，0，7，9，23，54，82，101。要求检索下列x的值：101，-14和82是否在a中出现。X=101X=-14X=82lowhighmi

4、dlowhighmidlowhighmid19519519569714269789811189899921找不到找到找到成功的检索不成功的检索成功的检索第10页/共37页2008-09-01第11页/共37页2008-09-01第12页/共37页2008-09-01public static int BINSRCH(int a,int n,int x) int low,high,mid,j; low=1;high=n;j=0; while(low=high) mid=(low+high)/2; if(xamid) low=mid+1; else j=mid; return j; return

5、j; 第13页/共37页2008-09-01成功检索 最好：1次 最坏：4次 平均：（3+2+3+4+1+3+2+3+4）/92.77次n不成功检索 最好：3次 最坏：4次 平均：(3+3+3+4+4+3+3+3+4+4)/10 = 3.4次 a 元素 -15 -6 0 7 9 23 54 82 101成功检索比较次数 3 2 3 4 1 3 2 3 4 不成功检索比较次数 3 3 3 4 4 3 3 3 4 4第14页/共37页2008-09-01二元比较树第15页/共37页2008-09-01注：外结点不代表元素的比较，因为比较过程在该外结点的上一级的内结点处结束。二元比较树第16页/共3

6、7页2008-09-01第17页/共37页2008-09-01n2k-1,2k)n最好最好情况下，成功检索的计算时间均为(1) n最坏最坏情况下，成功检索的计算时间均为(logn) 第18页/共37页2008-09-01第19页/共37页2008-09-01成功检索不成功检索最好平均最坏最好平均最坏(1)(logn) (logn) (logn) (logn) (logn)总结总结第20页/共37页2008-09-01只允许进行元素间的比较，而不允许对它们实施其它运算。第21页/共37页2008-09-01内结点：表示一次元素的比较，并代表成功检索情况。每棵比较 树中恰好含有n个内结点，分别与n

7、个不同i值相对应外结点：代表不成功检索情况。每棵比较树中恰好有n+1个外结点 分别与n+1中不成功检索情况相对应。第22页/共37页2008-09-01FIND(n)log(n+1) 证明：n 从模拟求解检索问题算法的比较树可知，FIND(n)不大于树中由根到一个叶子的最长路径的距离。n 在所有的二元比较树中必定有n个内结点分别与x在a中的n种可能的出现相对应。n如果一棵二元树的所有内结点所在的级数小于或等于k，则该树中最多有2k-1个内结点。 故，n2k-1,即FIND(n)log(n+1) 第23页/共37页2008-09-01第24页/共37页2008-09-01第25页/共37页200

8、8-09-01递归算法第26页/共37页2008-09-01算法的性能：只考虑算法中的比较运算，以此代表算法的执行特征；该算法最好、最坏、平均情况下均需要做2(n-1)次元素比较第27页/共37页2008-09-01第28页/共37页2008-09-01则有， MAX(I) = max(MAX(I1),MAX(I2) MIN(I) = min(MIN(I1),MIN(I2) MAX(I)和MIN(I)分别代表I中元素的最大者和最小者 采用递归的设计策略，得到以下算法：1I =( n/2 ,a1,a n/2 )2I =(n- n/2 ,a n/2 +1,an)第29页/共37页2008-09-0

9、1基本问题：只有一个元素基本问题：只有二个元素分治合并第30页/共37页2008-09-01i123456789ai2213-5-815601731471 , 9, - , -6 , 7, - , -1 , 5, - , -6 , 9, - , -4 , 5, - , -1 , 3, - , -8 , 9, - , -3, 3, - , -1 , 2, - , -121, 9, 60 ,-81, 2, 22 ,133, 3, -5 ,-531, 3, 22 ,-544, 5, 15 ,-851, 5, 22 ,-866, 7, 60 ,1778, 9, 47 ,3186, 9, 60 ,179第31页/共37页2008-09-0122)2()2(2110)(nnTnTnnnT用前面介绍的方法对此递归方程讨论。当n为2的幂时，即对于某个正数k，n=2k，有 22/32222)2(224)4/(42)2)4/(2(22)2/(2)(1111nTnTnTnTnTkkkiik第32页/共37页2008-09-0122/3n1