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

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

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

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

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

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

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

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

8、生成某一坐標(biāo)：iRandom(m,p-1)；調(diào)換am與ai;vai;aiam;im+1; 作用：將隨機(jī)指定的劃分元素的值調(diào)換到 am位置。算法主體不變。之后，仍從am開(kāi)始執(zhí)行劃分操作。2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 遞歸層次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個(gè)元素參加劃分和分類去掉1個(gè)第一級(jí)的劃分元素n-1個(gè)元素參加劃分和分類去掉2個(gè)第二級(jí)的劃分元素n

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

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

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

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

13、當(dāng)小的子文件分類完成后，再對(duì)較 大的子文件進(jìn)行分類。棧：需要一個(gè)棧空間保存目前暫不分類的較大子文件。并在較小子文件分類完成后，從棧中退出最新的較大子文件進(jìn)行下一步分類。?？臻g需求量：O(logn)算法終止：當(dāng)棧空時(shí)，整個(gè)分類過(guò)程結(jié)束。2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 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版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 快速分類算法迭代模型的空間分析設(shè)算法所需的最大?？臻g是S(n)，則有 2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 4.6 選擇問(wèn)題1. 問(wèn)題描述 在n個(gè)元素的表a1:n中確定第k小元素，1kn。2. 設(shè)計(jì)思路 利用Partition過(guò)程。在第一次劃分后劃分元素v測(cè)定在aj的位置上，則有j-1個(gè)元素小于或等于aj，且有n-j個(gè)元素大于或等于aj。此時(shí)， 若k=j，則aj即是第k小元素；否則， 若kj，則a1:n中的第k小元素將出現(xiàn)在aj+1:n， 是aj+1:n中的第k-j小元素。2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 利用

16、Partition實(shí)現(xiàn)的選擇算法public static void Select(int n,int k) /在數(shù)組a1,an中找第k小元素s并把它放在位置k，假設(shè)1kn。 /將剩下的元素按如下方式排列，使ak=t，對(duì)于1mk，有amt；對(duì)于 /kmn，有amt。an+1=+ int m,r,j; m=1;r=n+1;an+1=10000; while(true) /每當(dāng)進(jìn)入這一循環(huán)時(shí)，1mkrn+1 j=r; /將剩余元素的最大下標(biāo)加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版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 m=1;r=n+1;an+1=10000; while(true) j=r; j=Partition(m,j); if(k0，使得 ：因此， 劃分元素ik,將在i的前半部分求解2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 選擇cR(1)，對(duì)問(wèn)題規(guī)模n進(jìn)行歸納，證明對(duì)于所有n2，有R(n)4cn 歸納基礎(chǔ) 對(duì)于n=2由上式有 歸納假設(shè) 假定對(duì)于所有的n，2nm， R(n)4cn。 歸納步驟 對(duì)于n=m， 由于R(n)是n的非降函數(shù)，故可以得到當(dāng)m為偶數(shù)而k=m/2時(shí)，或者當(dāng)m為奇數(shù)而

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

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

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

21、artition劃分a，v作為劃分元素。 假設(shè)v在位置j。 case k=j: return(v); kj: 設(shè)S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:設(shè)R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 算法分析記T(n)是Select2所需的最壞情況時(shí)間對(duì)特定的r分析Select2，選取r=5。(a中的元素各不相同)2008-09-01版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院 public static int Select2(int a,int k,int n)

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

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