算法分析與設計第四章(分治法快速分類)課件

1、第四章 分治法2008-09-01版權所有：楊波，武漢科技大學理學院 4.5 快速分類1.劃分與快速分類 快速分類是一種基于劃分的分類方法； 劃分：選取待分類集合A中的某個元素t，按照與t的大小關系重 新整理A中元素，使得整理后t被置于序列的某位置上， 而序列中所有在t以前出現(xiàn)的元素均小于等于t，而所有出 現(xiàn)在t以后的元素均大于等于t。這一元素的整理過程稱為 劃分（Partitioning）。 元素t稱為劃分元素。 快速分類：通過反復地對待排序集合進行劃分達到分類目的的分類算法。2008-09-01版權所有：楊波，武漢科技大學理學院 快速分類的基本思想 對于輸入的子數(shù)組am:p-1，按以下3個

2、步驟進行排序： 分解（divide）：以am為基準元素（假定第一個元素am是劃分元素）將am:p-1分成3段am:q-1，aq和aq+1:p-1，使得am:q-1中任何元素小于等于aq，aq+1:p-1中任何元素大于等于aq，下標q 在劃分過程中確定。 遞歸求解（conquer）：通過遞歸調用快速排序算法，分別對am:q-1和aq+1:p-1進行排序。 合并（merge）：由于對 am:q-1和aq+1:p-1的排序是就地進行的，所以在am:q-1和aq+1:p-1都已排好序后不需要執(zhí)行任何計算，am:p-1就已排好序 。2008-09-01版權所有：楊波，武漢科技大學理學院 劃分過程的算法描

3、述public static int Partition(int m,int p)/在am，am+1，ap-1中的元素按如下方式重新排列：如果最初t=am，則在重排完成之后， /對于m和p-1之間的某個q，有aq=t，并使得對于mkq，有ak t，而對于qkp，有ak t。 /退出時返回值為劃分元素所在的下標位置 int i,v;/v為劃分元素，i為從左到右計數(shù)，p從右到左計數(shù) v=am;i=m+1;p=p-1; int temp;/臨時交換單元 while(true) while(aiv) p-;/直到不大于v,p向左移動 if(ip) /ai與ap交換位置 temp=ai; ai=ap;

4、ap=temp; else break; am=ap;ap=v; /劃分元素在位置p return p;ap被定義，但為一限界值apam ，不包含在實際的分類區(qū)間內(nèi)。(技巧：假如是按照從大到小排列，經(jīng)過Partition算法之后進行從小到大排列，引入ap則程序易于實現(xiàn)）算法對集合am:p-1進行劃分元素am作為劃分元素2008-09-01版權所有：楊波，武漢科技大學理學院 劃分實例（1次劃分）12345678910iP65707580856055504510000296545758085605550701000038654550808560557570100004765455055856080

5、757010000566545505560858075701000065604550556585807570100005Partition(m,p)=Partition(1,10)劃分元素p=52008-09-01版權所有：楊波，武漢科技大學理學院 經(jīng)過一次“劃分”后，實現(xiàn)了對集合元素的調整： 以劃分元素為界，左邊子集合的所有元素均小于等于右邊子集合的所有元素。 按同樣的策略對兩個子集合進行分類處理。當子集合分類完畢后，整個集合的分類也完成了。這一過程避免了子集合的歸并操作。這一分類方法稱為快速分類。2008-09-01版權所有：楊波，武漢科技大學理學院 快速分類算法public static

6、 void QuickSort(int p,int q)/將全程數(shù)組a1:n中的元素ap，aq按遞增的方式分類。 /認為an+1已被定義，且大于或等于ap:q的所有元素；即an+1=+ int j; if(pq) j=q+1;/每次執(zhí)行Partition時使用一個右側附加空間p:q等同與m:p-1 /m=p;p-1=q; j=Partition(p,j);/j是劃分元素的位置 QuickSort(p,j-1);/對左半段排序 QuickSort(j+1,q);/對右半段排序 2008-09-01版權所有：楊波，武漢科技大學理學院 全部分類過程12345678916570758085605550

7、4526045505565858075703554550606585807570450455560658580757054550556065858075706455055606585807570745505560657080758584550556065708075859455055606570758085104550556065707580852008-09-01版權所有：楊波，武漢科技大學理學院 快速分類分析統(tǒng)計的對象：元素的比較次數(shù)，記為：C(n)兩點假設參加分類的n個元素各不相同Partition中的劃分元素v是隨機選取的（針對平均情況的分析）隨機選取劃分元素：在劃分區(qū)間m,p-1隨機

8、生成某一坐標：iRandom(m,p-1)；調換am與ai;vai;aiam;im+1; 作用：將隨機指定的劃分元素的值調換到 am位置。算法主體不變。之后，仍從am開始執(zhí)行劃分操作。2008-09-01版權所有：楊波，武漢科技大學理學院 遞歸層次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1+1,n)QuickSort(1,j21-1)QuickSort(j21+1, j1-1)QuickSort(j1+1,j22-1)QuickSort(j22+1,n)n個元素參加劃分和分類去掉1個第一級的劃分元素n-1個元素參加劃分和分類去掉2個第二級的劃分元素n

9、-3個元素參加劃分和分類去掉4個第三級的劃分元素第一層第二層第三層 設在任一級遞歸調用上，調用Partition處理的所有元素總數(shù)為r，則，初始時r=n，以后的每級遞歸上，由于刪去了上一級的劃分元素，故r比上一級至少1：理想情況，（與前一級相比）第二級少1，第三級少2，第四級少4， ；最壞情況，每次僅減少1（每次選取的劃分元素剛好是當前集合中最小或最大者）2008-09-01版權所有：楊波，武漢科技大學理學院 最壞情況分析記最壞情況下的元素比較次數(shù)是Cw(n)；設r是在任一級遞歸上對Partition的所有調用的元素總數(shù)。在一級只有一次調用，執(zhí)行Partition(1,n+1)，且r=n，因此

10、，比較數(shù)至多是n+1；在二級至多作兩次調用（一次實際不做任何處理），且r=n-1，因此，比較數(shù)至多是n等等。因此，在遞歸的任意一級上，所有的Partition共作r+1次元素比較，而每一級的r，由于刪去了前一級的劃分元素，故比前一級的r至少要少1。Cw(n)是r由n變到2的和，即Cw(n)=O(n2)。2008-09-01版權所有：楊波，武漢科技大學理學院 最壞情況舉例k01234n-1nn+1ak-n123n-2n-1漸近時間復雜度2008-09-01版權所有：楊波，武漢科技大學理學院 最好情況下漸近時間復雜度2008-09-01版權所有：楊波，武漢科技大學理學院 平均情況分析 平均情況是指

11、集合中的元素以任意順序排列，且任選元素作為劃分元素進行劃分和分類，在這些所有可能的情況下，算法執(zhí)行性能的平均值。 設調用Partition(m,p)時，所選取劃分元素v恰好是am:p-1中的第i小元素（1ip-m）的概率相等。則經(jīng)過一次劃分，所留下的待分類的兩個子文件恰好是am:j-1和aj+1:p-1的概率是：1/(p-m), mjp。 記平均情況下的元素比較次數(shù)是CA(n)；則有： 其中， n+1是Partition第一次調用時所需的元素比較次數(shù)。 CA(0) = CA(1) = 0(1)2008-09-01版權所有：楊波，武漢科技大學理學院 用n-1換(2)中的n (2)-(3) 即 反

12、復使用(4)代換CA(n-1)，CA(n-2)，得到 2008-09-01版權所有：楊波，武漢科技大學理學院 由于 所以 2008-09-01版權所有：楊波，武漢科技大學理學院 空間分析 最壞情況下，遞歸的最大深度為n-1. 需要?？臻g：O(n) 使用一個迭代模型可以將?？臻g總量減至O(logn)最壞時間復雜度：O(n2)平均時間復雜度：O(nlogn)輔助空間：O(n)或O(logn)2008-09-01版權所有：楊波，武漢科技大學理學院 快速分類算法的迭代模型處理策略：每次在Partition將文件A(p:q)分成兩個文件A(p:j-1)和A(j+1,q)后，先對其中較小的子文件進行分類。

13、當小的子文件分類完成后，再對較 大的子文件進行分類。棧：需要一個?？臻g保存目前暫不分類的較大子文件。并在較小子文件分類完成后，從棧中退出最新的較大子文件進行下一步分類。?？臻g需求量：O(logn)算法終止：當?？諘r，整個分類過程結束。2008-09-01版權所有：楊波，武漢科技大學理學院 QuickSort的迭代模型 public static void QuickSort2(int p,int q) int stack,top,j; stack=new int11; top=0; while(true) while(pq) j=q+1; j=Partition(p,j); if(j-pq-j

14、) stacktop+1=j+1; stacktop+2=q; q=j-1;/左半文件較小先處理 /將大的子文件入棧后處理 else stacktop+1=p; stacktop+2=j-1; p=j+1;/右半文件較小先處理 top=top+2; if(top=0) break; q=stacktop;p=stacktop-1; top=top-2; public static void QuickSort(int p,int q) int j; if(pq) j=q+1 j=Partition(p,j); QuickSort(p,j-1); QuickSort(j+1,q); 2008-0

15、9-01版權所有：楊波，武漢科技大學理學院 快速分類算法迭代模型的空間分析設算法所需的最大?？臻g是S(n)，則有 2008-09-01版權所有：楊波，武漢科技大學理學院 4.6 選擇問題1. 問題描述 在n個元素的表a1:n中確定第k小元素，1kn。2. 設計思路 利用Partition過程。在第一次劃分后劃分元素v測定在aj的位置上，則有j-1個元素小于或等于aj，且有n-j個元素大于或等于aj。此時， 若k=j，則aj即是第k小元素；否則， 若kj，則a1:n中的第k小元素將出現(xiàn)在aj+1:n， 是aj+1:n中的第k-j小元素。2008-09-01版權所有：楊波，武漢科技大學理學院 利用

16、Partition實現(xiàn)的選擇算法public static void Select(int n,int k) /在數(shù)組a1,an中找第k小元素s并把它放在位置k，假設1kn。 /將剩下的元素按如下方式排列，使ak=t，對于1mk，有amt；對于 /kmn，有amt。an+1=+ int m,r,j; m=1;r=n+1;an+1=10000; while(true) /每當進入這一循環(huán)時，1mkrn+1 j=r; /將剩余元素的最大下標加1后給j j=Partition(m,j); /返回j，它使得aj是第j小的值 if(kj) r=j; /j是新的上界 else if(k=j) return

17、; else m=j+1; /j+1是新的下界 2008-09-01版權所有：楊波，武漢科技大學理學院 m=1;r=n+1;an+1=10000; while(true) j=r; j=Partition(m,j); if(k0，使得 ：因此， 劃分元素ik,將在i的前半部分求解2008-09-01版權所有：楊波，武漢科技大學理學院 選擇cR(1)，對問題規(guī)模n進行歸納，證明對于所有n2，有R(n)4cn 歸納基礎 對于n=2由上式有 歸納假設 假定對于所有的n，2nm， R(n)4cn。 歸納步驟 對于n=m， 由于R(n)是n的非降函數(shù)，故可以得到當m為偶數(shù)而k=m/2時，或者當m為奇數(shù)而

18、k=(m+1)/2時，取極大值。因此 若m為偶數(shù)，則 若m為奇數(shù)，則 由于 TA(n)R(n)，所以TA(n)4cn，故TA(n)=O(n)2008-09-01版權所有：楊波，武漢科技大學理學院 最壞情況時間是O(n)的選擇算法基本思想：精心挑選劃分元素v方法：二次取中間值目的：使v比一部分元素小比另一部分元素大2008-09-01版權所有：楊波，武漢科技大學理學院 二次取中間值作為劃分元素v 首先，將參加劃分的n個元素分成 組，每組有r個元素(r1)。（多余的 個元素忽略不計） 然后，對這 組每組的r個元素進行分類并找出其中間元素mi,1i ，共得 個中間值。 之后，對這 個中間值分類，并找

19、出其中間值mm。將mm作為劃分元素執(zhí)行劃分。2008-09-01版權所有：楊波，武漢科技大學理學院 例：設n=35，r=7。分為n/r=5個元素組：B1，B2，B3，B4，B5，每組7個元素。每組7個元素沿列而下已排成一個非降序列。 每列中間的元素就是mi。而且這些列也按的mi非降次序進行排列。因此，第3列的mi就是mm。mm中間值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列2008-09-01版權所有：楊波，武漢科技大學理學院 由于r個元素的中間值是第 小元素。則， 至少有 個mi小于或等于mm； 至少有 個mi大于或等于mm。 故，至少有

20、個元素小于或等于（或大于或等于）mm。 當r=5，則使用兩次取中間值規(guī)則來選擇v=mm，可得到， 至少有 個元素小于或等于選擇元素v。 且至多有 個元素大于v。 同理，至多有 0.7n+1.2個元素小于v。 故，這樣的v可較好地劃分a中的n個元素。2008-09-01版權所有：楊波，武漢科技大學理學院 使用二次取中規(guī)則的選擇算法的說明性描述public static int Select2(int a,int k,int n) /在集合a中找第k小元素 若nr，則采用插入法直接對a分類并返回第k小元素。 把a分成大小為r的 個子集合，忽略剩余的元素。 設 是上面 個子集合的中間值的集合。 用P

21、artition劃分a，v作為劃分元素。 假設v在位置j。 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)2008-09-01版權所有：楊波，武漢科技大學理學院 算法分析記T(n)是Select2所需的最壞情況時間對特定的r分析Select2，選取r=5。(a中的元素各不相同)2008-09-01版權所有：楊波，武漢科技大學理學院 public static int Select2(int a,int k,int n)

22、/在集合a中找第k小元素 若nr，則采用插入法直接對a分類并返回第k小元素。 把a分成大小為r的 個子集合，忽略剩余的元素。 設 是上面 個子集合的中間值的集合。 用Partition劃分a，v作為劃分元素。 假設v在位置j。 case k=j: return(v); kn 兩個子問題的規(guī)模和大于原問題。 改進： 取r=9。經(jīng)計算可得，此時將有 個元素小于或等于v，同時至少有 大于或等于v。 則當n90時，|S|和|R|都至多為：public static int Select2(int a,int k,int n) /在集合a中找第k小元素 case k=j: return(v); kj:

23、設S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:設R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)T(n)T(n/5)+T(3n/4)+cn2008-09-01版權所有：楊波，武漢科技大學理學院 用歸納法可證：T(n)72c1n即：T(n)=O(n)2008-09-01版權所有：楊波，武漢科技大學理學院 Select2的實現(xiàn)算法中需要解決的兩個問題 1) 如何確定子集合的中間值 當r較小時，采用InsertionSort(a,i,j)直接對每組的r個元素分類，在分類好的序列中，中間元素即為當前r個元素中的中間位置下標對應的元素。 2) 如何保存 個子集合的中間值 注：各組找到的中間元素值將調整到數(shù)組a的前部，連續(xù)保存，從而可用遞歸調用