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

1、会计学1 算法分析与设计分治法快速分类概要算法分析与设计分治法快速分类概要 2008-09-01 第1页/共48页 2008-09-01 第2页/共48页 2008-09-01 ap被定义，但为一限界值apam ，不包含在实际的分类区间内。(技巧技巧：假如是按照从大到小排列，经过Partition算法之后进行从小到大排列，引入ap则程序易于实现） 算法对集合am:p-1进行划分 元素am作为划分元素 第3页/共48页 2008-09-01 12345678910iP 65 70 75 80 85 60 55 50 45 10000 29 65 45 75 80 85 60 55 50 70 1

2、0000 38 65 45 50 80 85 60 55 75 70 10000 47 65 45 50 55 85 60 80 75 70 10000 56 65 45 50 55 60 85 80 75 70 10000 65 60 45 50 55 65 85 80 75 70 100005 Partition(m,p)=Partition(1,10) 划分元素 p=5 第4页/共48页 2008-09-01 作。这一分类方法称为快速分类。 第5页/共48页 2008-09-01 第6页/共48页 2008-09-01 123456789 1657075808560555045 2604

3、550556585807570 3554550606585807570 4504555606585807570 5455055606585807570 6455055606585807570 7455055606570807585 8455055606570807585 9455055606570758085 10455055606570758085 第7页/共48页 2008-09-01 第8页/共48页 2008-09-01 QuickSort(1,n) QuickSort(1,j1-1)QuickSort(j1+1,n) QuickSort(1,j21-1)QuickSort(j21+1

4、, j1-1)QuickSort(j1+1,j22-1)QuickSort(j22+1,n) n个元素参加划分和分类 去掉1个第一级的划分元素 n-1个元素参加划分和分类 去掉2个第二级的划分元素 n-3个元素参加划分和分类 去掉4个第三级 的划分元素 第一层 第二层 第三层 设在任一级递归调用上，调用Partition处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1： 理想情况，（与前一级相比）第二级少1，第三级少2，第四级少4， ； 最坏情况，每次仅减少1（每次选取的划分元素刚好是当前集合中最小或最大者） 第9页/共48页 2008

5、-09-01 第10页/共48页 2008-09-01 k01234n-1nn+1 ak-n123n-2n-1 32 ( ) 1(1)2 W W n Cn nCnn )()( 2 nnCW 渐近时间复杂度 第11页/共48页 2008-09-01 32 ( ) 2(1)/2)12 B B n Cn Cnnn ( )( log ) B Cnnn 渐近时间复杂度 第12页/共48页 2008-09-01 其中， n n+1是Partition第一次调用时所需的元素比较次数。 n CA(0) = CA(1) = 0 nk AAnA knCkCnnC 1 1 )() 1(1)( (1) 第13页/共4

6、8页 2008-09-01 n) 1 ( )2()1() 1 ()0(2) 1()(nCCCnnnnC AAAA 用n-1换(2)中的n (1)(1)(1)2(0)(1)(2)(3) AAAA nCnn nCCCn (2)-(3) ) 1(22) 1() 1()(nCnnCnnnC AAA 即 )4() 1/(2/ ) 1() 1/()(nnnCnnC AA 反复使用(4)代换CA(n-1)，CA(n-2)，得到 第14页/共48页 2008-09-01 13 /122/ ) 1 ( ) 1/(2/2) 1/(2)2/() 3( ) 1/(2/2) 1/()2() 1/()( nk A A A

7、A kC nnnnnC nnnnCnnC 由于 1 2 13 ) 1ln(/1 n nk n x dx k 所以 )log() 1ln() 1(2)(nnnnnCA 第15页/共48页 2008-09-01 使用一个迭代模型可以将栈空间总量减至O(logn) if(pq) j=q+1 j=Partition(p,j); QuickSort(p,j-1); QuickSort(j+1,q); 第18页/共48页 2008-09-01 10 1)2/ ) 1(2 )( n nnS nS 第19页/共48页 2008-09-01 第20页/共48页 2008-09-01 第21页/共48页 2008

8、-09-01 m=1;r=n+1;an+1=10000; while(true) j=r; j=Partition(m,j); if(kj) r=j; else if(k=j) return; else m=j+1; 第22页/共48页 2008-09-01 两点假设 a中的元素互异 随机选取划分元素，且选择am:p-1中任一元素作为划分元 素的概率相同 分析 n 在Select中每次调用Partition(m,j)，所需的元素比较次数是 j-m+1。 n 在执行一次Partition后，或者找到第k小元素，或者将 在缩小的子集(am,k-1或ak+1,j)中继续查找。缩小 的子集的元素数将至

9、少比上一次划分的元素数少少1。 第23页/共48页 2008-09-01 )() ) 1( 2 1 ni n 第24页/共48页 2008-09-01 是找a1:n的第k小元素的平均时间；TA(n) 是 )(nT k A Select的平均计算时间。则有： nk k AA nT n nT 1 )( 1 )( 定义 )(max)(nTnR k A k 则有： ( )( ) A TnR n 对n个不同的元素，问题实例可能的n!种不同情况，综合考查所得的平均值 在所有可能的情况下，找所有可能的k小元素 某个特定的k 第25页/共48页 2008-09-01 2) 1()( 1 )( 1 niTinT

10、 n cnnT kinik k A ik A k A 因此， 1 11 1 1 ( )max()(1) 1 max( )( )2 k i kk i n nn k n kk R ncnR niR i n cnR iR in n 划分元素ik,将在i的前半部分求解 第26页/共48页 2008-09-01 选择cR(1)，对问题规模n进行归纳，证明对于所有n2，有R(n)4cn 归纳基础归纳基础 对于n=2由上式有 1 (2)2max(1), (1)2.54 2 RcRRccn 归纳假设归纳假设 假定对于所有的n，2nm， R(n)4cn。 归纳步骤归纳步骤 对于n=m， 11 1 1 ( )ma

11、x( )( ) mm k m kk R mcmR iR i m 由于R(n)是n的非降函数，故可以得到当m为偶数而k=m/2时，或者当m为 奇数而k=(m+1)/2时， 11 1 )()( m k m km iRiR取极大值。因此 若m为偶数，则 11 /2/2 28 ( )( )4 mm mm c R mcmR icmicm mm 若m为奇数，则 11 (1)/2(1)/2 28 ( )( )4 mm mm c R mcmR icmicm mm 由于 TA(n)R(n)，所以TA(n)4cn，故TA(n)=O(n) 第27页/共48页 2008-09-01 第28页/共48页 2008-09

12、-01 n/r n/rrn n/r n/r n/r n/r 第29页/共48页 2008-09-01 mm 中间值 小于等于mm的元素 大于等于mm的元素 非 降 次 序 B1 B2 B3 B4 B5 按照mi的非降次序排列 第30页/共48页 2008-09-01 /2n/r1/2n/rn/r 2/n/r r/2 n/55 . 1 n1.5 n/50.7n1.2 /2n/rr/2 505 1.5/551.5 50.3 5 0.7 5 0.7(5)0.3 0.70.3 0.71.2 nkmm nnkmk kkm km kmm nm n 第31页/共48页 2008-09-01 rn/ rn m

13、mmM /21 , rn/ 2(,/2 ,/)vSelectMn rn r 第32页/共48页 2008-09-01 第33页/共48页 2008-09-01 rn/ rn mmmM /21 , rn/ 2(,/2 ,/)vSelectMn rn r O(1 ) O( n) O(1 ) O( n) T(n/ 5) O( n) T(3n/ 4) |,| 0.7123 /4,24SRnnn 第34页/共48页 2008-09-01 第35页/共48页 2008-09-01 第36页/共48页 2008-09-01 2.5 n/9 2.5 n/9 1 n-2.5 n/9 +(2.5 n/9 )=n-

14、1.25 n/931n/36+1.2563n/72 2 public static int Select2(int a,int k,int n) /在集合a中找第k小元素 case k=j: return(v); kj: 设S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:设R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j) 2(,/2 ,/)vSelectMn rn r T(n)T(n/5)+T(3n/4)+cn 第37页/共48页 2008-09-01 1 1 90 ( ) ( /9)(63 /72)90 c nn T n

15、 T nTnc nn 用归纳法可证： T(n)72c1n 即： T(n)=O(n) 第38页/共48页 2008-09-01 式对这些中间值进行排序并找 出中间值的中间值。 rn/ 第39页/共48页 2008-09-01 public static int Sel(int m,int p,int k) /返回一个i，使得i属于m,p，且ai是am:p中第k小元素，r是一个全程变量，其取值为一个大于1的整数。 int i,j,n,temp; if(p-m+1=r) InsertionSort(m,p); return(m+k-1);/返回第k小元素的位置 while(true) n=p-m+1

16、; /元素数 for(i=1;ik) p=j-1; else k=k-(j-m+1); m=j+1; 第40页/共48页 2008-09-01 第41页/共48页 2008-09-01 111211121112 212221222122 AABBCC AABBCC 其中： 1111111221 1211121222 2121112221 2221122222 CA BA B CA BA B CA BA B CA BA B 第42页/共48页 2008-09-01 2)2/(8 2 )( 2 ndnnT nb nT )()( 3 nnT 渐近复杂度 第43页/共48页 2008-09-01 技巧：增加加法减少乘法 第44页/共48页 2008-09-01 11221122 212211 111222 222111 111222 21111112 12222122 ()() () () () () ()() ()() PAABB QAAB RABB SABB TAAB UAABB VAABB 则： 11