(算法分析設(shè)計(jì))第2章遞歸與分治策略課件

1、第2章 遞歸與分治策略第2章 遞歸與分治策略學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過(guò)下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。（1）二分搜索技術(shù)； （2）大整數(shù)乘法；（3）Strassen矩陣乘法；（4）合并排序（5）快速排序；（6）線性時(shí)間選擇；學(xué)習(xí)要點(diǎn):將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。算法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 對(duì)這k個(gè)子問(wèn)題分別求解。如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題，如此遞歸的進(jìn)行下去，直到問(wèn)題規(guī)模足夠小，很容易求出其解為止。將要求解的較大規(guī)模的問(wèn)題分割成k個(gè)更小規(guī)模的子問(wèn)題。算法總體(算法分析設(shè)計(jì)

2、)第2章遞歸與分治策略課件(算法分析設(shè)計(jì))第2章遞歸與分治策略課件2.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用。2.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。2.1 遞歸的概念例1 階乘函數(shù) 非遞歸定義：n！=n*(n-1)*(n-2)*1 階乘函數(shù)可遞歸地定義為：邊界條件遞歸方

3、程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素。2.1 遞歸的概念例1 階乘函數(shù)邊界條件遞歸方程邊界條件遞歸算法：int recur(int n) if (n = 1) return 1; return n*recur(n-1); 遞歸出口遞歸調(diào)用遞歸算法：遞歸出口遞歸調(diào)用2.1 遞歸的概念例2 Fibonacci數(shù)列無(wú)窮數(shù)列1，1，2，3，5，8，13，21，34，55，稱為Fibonacci數(shù)列。它可以遞歸地定義為：邊界條件遞歸方程第n個(gè)Fibonacci數(shù)可遞歸地計(jì)算如下：int fibonacci(int n) if (n 0) hanoi(n-1, a, c, b); move(a,b);

4、 hanoi(n-1, c, b, a); 表示以塔座b為輔助塔座，將塔座上自下而上，由大到小疊在一起的-1個(gè)圓盤(pán)按規(guī)則移至塔座上并按同樣順序疊放。將塔座a上的圓盤(pán)移動(dòng)到塔座b上去void hanoi(int n, int a, int bHanoi塔問(wèn)題的復(fù)雜性分析=1移動(dòng)次數(shù)（）移動(dòng)次數(shù)（）移動(dòng)次數(shù)（）移動(dòng)次數(shù)（）當(dāng)時(shí)移動(dòng)次數(shù)（）？Hanoi塔問(wèn)題的復(fù)雜性分析=1遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來(lái)很大方便。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無(wú)論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀

5、性強(qiáng)，而且容易用數(shù)學(xué)歸納法來(lái)證明求Fibonacci數(shù)時(shí)有很多重復(fù)工作：求Fibonacci數(shù)時(shí)有很多重復(fù)工作：解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個(gè)用戶定義的棧來(lái)模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過(guò)人工做了本來(lái)由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來(lái)實(shí)現(xiàn)遞歸函數(shù)。3、通過(guò)變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。遞歸小結(jié)解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。遞分治法的基本思想分治法的基本思想將一個(gè)規(guī)模為n的問(wèn)題分解為a個(gè)規(guī)模較小的子問(wèn)題，這些

6、子問(wèn)題互相獨(dú)立并且與原問(wèn)題相同。通過(guò)遞歸地求解這些子問(wèn)題，然后再將各個(gè)子問(wèn)題的解合并，就可以實(shí)現(xiàn)對(duì)原問(wèn)題的求解。分治法的基本思想分治法的基本思想分治法的求解過(guò)程分治法的求解過(guò)程分解(divide)：將原問(wèn)題分解為一系列子問(wèn)題；遞歸求解(conquer)：遞歸求解各個(gè)子問(wèn)題。若子問(wèn)題足夠小，則直接求解。合并(merge)：將子問(wèn)題結(jié)果合并成原問(wèn)題的解說(shuō)明：某些問(wèn)題不需要合并，比如二分搜索問(wèn)題分治法的求解過(guò)程分治法的求解過(guò)程divide-and-conquer(P) if(|P|=n0) adhoc(P); divide P into smaller subinstances P1,P2,Pa;

7、for(i=1,i=a,i+) yi= divide-and-conquer(Pi); return merge(y1,y2,ya);|P|：?jiǎn)栴}P的規(guī)模；adhoc：分治法中的基本子運(yùn)算n0：閥值如果問(wèn)題P的規(guī)模不超過(guò)n0，說(shuō)明問(wèn)題已經(jīng)容易求解，不要再繼續(xù)分解。利用adhoc(P)直接求解。分治法的設(shè)計(jì)模式divide-and-conquer(P)|P|：?jiǎn)栴}P的規(guī)分治法的分割原則分治法的分割原則實(shí)踐表明：將一個(gè)問(wèn)題劃分成數(shù)據(jù)規(guī)模大小相等的a個(gè)子問(wèn)題的處理方法行之有效；分治法的分割原則分治法的分割原則分治法的計(jì)算效率分析分治法的計(jì)算效率分析通常用遞歸方程來(lái)進(jìn)行分析分治法將規(guī)模為n的問(wèn)題分成a

8、個(gè)規(guī)模為n/b的子問(wèn)題設(shè)分解閾值n0=1，且adhoc解規(guī)模為1的問(wèn)題耗費(fèi)1個(gè)單位時(shí)間設(shè)將原問(wèn)題分解為a個(gè)子問(wèn)題以及用merge將a個(gè)子問(wèn)題的解合并為原問(wèn)題解需要使用f(n)個(gè)單位時(shí)間。用T(n)表示該分治法divide-and-merge(P)解規(guī)模為|P|=n的問(wèn)題所需要的計(jì)算時(shí)間分治法的計(jì)算效率分析分治法的計(jì)算效率分析(算法分析設(shè)計(jì))第2章遞歸與分治策略課件g(n)函數(shù)g(n)函數(shù)g(n)函數(shù)g(n)函數(shù)T(n)函數(shù)g(n)函數(shù)g(n)函數(shù)T(n)函數(shù)主方法(詳見(jiàn)算法導(dǎo)論)根據(jù)這兩項(xiàng)對(duì)結(jié)果的影響不同，分成三種情況討論主方法(詳見(jiàn)算法導(dǎo)論)根據(jù)這兩項(xiàng)對(duì)結(jié)果的影響不同，分成三(算法分析設(shè)計(jì))

9、第2章遞歸與分治策略課件因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部分問(wèn)題滿足這個(gè)特征。這條特征是應(yīng)用分治法的前提，它也是大多數(shù)問(wèn)題可以滿足的，此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問(wèn)題是否具有這條特征，如果具備了前兩條特征，而不具備第三條特征，則可以考慮貪心算法或動(dòng)態(tài)規(guī)劃。這條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即

10、該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子問(wèn)題。 因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加，因此大部二分搜索技術(shù)大整數(shù)的乘法Strassen矩陣乘法合并排序快速排序線性時(shí)間選擇二分搜索技術(shù)二分搜索技術(shù)二分搜索技術(shù)分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問(wèn)題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無(wú)論是在前面還是后面查找x，其方

11、法都和在a中查找x一樣，只不過(guò)是查找的規(guī)模縮小了。這就說(shuō)明了此問(wèn)題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問(wèn)題分解出的子問(wèn)題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問(wèn)題，因此滿足分治法的第四個(gè)適用條件。二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。分析：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決；該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題;分解出的子問(wèn)題的解可以合并為原問(wèn)題的解；分解出的各個(gè)子問(wèn)題是相互獨(dú)立的。 分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以逐個(gè)地掃描數(shù)組a中每個(gè)元素，直到找到x為止。在含有n個(gè)元素的線

12、性表中查找一個(gè)元素在最壞情況下都需要進(jìn)行n次比較，其時(shí)間復(fù)雜度為O(n)。利用分治法求解此問(wèn)題,求解過(guò)程是：將n個(gè)元素分成個(gè)數(shù)大致相等彼此獨(dú)立的兩半部分，即an/2的前面或后面兩個(gè)子問(wèn)題；將第n/2位置的元素與x進(jìn)行比較，如果相等，則找到x，算法結(jié)束。如果xan/2,則在數(shù)組a的后半部分繼續(xù)搜索x；如果xan/2,則在數(shù)組a的前半部分繼續(xù)搜索x。逐個(gè)地掃描數(shù)組a中每個(gè)元素，直到找到x為止。二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法：template int BinarySearch(Type a, const Type&

13、 x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x am) r = m-1; else l = m+1; return -1; 算法復(fù)雜度分析：每執(zhí)行一次算法的while循環(huán)， 待搜索數(shù)組的大小減少一半。因此，在最壞情況下，while循環(huán)被執(zhí)行了O(logn) 次。循環(huán)體內(nèi)運(yùn)算需要O(1) 時(shí)間，因此整個(gè)算法在最壞情況下的計(jì)算時(shí)間復(fù)雜性為O(logn) 。二分搜索技術(shù)給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)大整數(shù)的乘法大整數(shù)的乘法大整數(shù)的乘法大整數(shù)的乘法問(wèn)題描述需要處理的整數(shù)超過(guò)了計(jì)算機(jī)硬

14、件能直接處理的整數(shù)范圍浮點(diǎn)數(shù)計(jì)算對(duì)精度的影響解決方案利用軟件方法來(lái)實(shí)現(xiàn)大整數(shù)的乘法典型應(yīng)用RSA密碼體系大整數(shù)的乘法大整數(shù)的乘法 傳統(tǒng)做法：需要做n*n次1位整數(shù)乘法操作，n-1次移位操作，n-1次加法操作時(shí)間復(fù)雜度為O(n2) 傳統(tǒng)做法：n/2位n/2位ABX=n/2位n/2位CDY=大整數(shù)X和Y的分段X、Y為兩個(gè)n位的二進(jìn)制整數(shù)n/2位n/2位ABX=n/2位n/2位CDY=大整數(shù)X和YXY的乘積形式（1/2）形式一：包括：4次n/2位整數(shù)的乘法3次不超過(guò)2n位的整數(shù)加法2次移位XY的乘積形式（1/2）形式一：包括：所有加法和移位共用O(n)步運(yùn)算設(shè)T(n)是2個(gè)n位整數(shù)相乘所需的運(yùn)算總數(shù)

15、所有加法和移位共用O(n)步運(yùn)算XY的乘積形式（2/2）形式二：包括：3次n/2位整數(shù)的乘法6次整數(shù)加、減法2次移位XY的乘積形式（2/2）形式二：包括：如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，將有可能得到更優(yōu)的算法。最終的，這個(gè)思想導(dǎo)致了快速傅利葉變換(Fast Fourier Transform)的產(chǎn)生。該方法也可以看作是一個(gè)復(fù)雜的分治算法，對(duì)于大整數(shù)乘法，它能在O(nlogn)時(shí)間內(nèi)解決。是否能找到線性時(shí)間的算法？目前為止還沒(méi)有結(jié)果。如果將大整數(shù)分成更多段，用更復(fù)雜的方式把它們組合起來(lái)，將有可Strassen矩陣乘法Strassen矩陣乘法矩陣的乘法：矩陣的乘法：(算法分析

16、設(shè)計(jì))第2章遞歸與分治策略課件Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫(xiě)為：傳統(tǒng)方法：O(n3)分治法:由此可得：復(fù)雜度分析T(n)=O(n3)2個(gè)n階矩陣的乘積轉(zhuǎn)化為計(jì)算8個(gè)n/2階矩陣的乘積和4個(gè)n/2階矩陣的和。2個(gè)(n/2)*(n/2)階的矩陣加法可以在O(n2)時(shí)間內(nèi)完成Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和Strassen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫(xiě)為：傳統(tǒng)方法：O(n3)分治法:由此可得：Str

17、assen矩陣乘法使用與上例類似的技術(shù)，將矩陣A，B和Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。復(fù)雜度分析T(n)=O(nlog7) =O(n2.81)較大的改進(jìn)做了7次乘法運(yùn)算；做了18次加減法運(yùn)算；Strassen矩陣乘法傳統(tǒng)方法：O(n3)為了降低時(shí)間復(fù)雜分解：將n階矩陣A、B分解為n/2階子矩陣；解決：進(jìn)行7次遞歸計(jì)算(n/2)*(n/2)子矩陣的乘積；合并：按C的子矩陣，對(duì)子矩陣的乘積進(jìn)行加減法運(yùn)算；Strassen分治策略分解：將n階矩陣A、B分解為n/2階子矩陣；StrassenStrassen矩陣乘法更快的方法?Hopcroft

18、和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究或矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是 O(n2.376)是否能找到O(n2)的算法？Strassen矩陣乘法更快的方法?Hopcroft和Ke合并排序合并排序合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，分別對(duì)2個(gè)子集合進(jìn)行排序，最終將排好序的子集合合并成為所要求的排好序的集合。 void mergesort(Type a, int lef

19、t, int right) if (leftright) /至少有2個(gè)元素 int i=(left+right)/2; /取中點(diǎn) mergesort(a, left, i); mergesort(a, i+1, right); merge(a, b, left, i, right); /合并到數(shù)組b copy(a, b, left, right); /復(fù)制回?cái)?shù)組a merge和copy可以在O(n)時(shí)間內(nèi)完成，復(fù)雜度分析T(n)=O(nlogn) 漸近意義下的最優(yōu)算法算法mergesort遞歸地調(diào)用自身，不斷將子序列分成兩個(gè)更小的子序列算法merge合并兩個(gè)排好序的數(shù)組到新數(shù)組b中算法copy

20、將合并后的數(shù)值段再?gòu)?fù)制到數(shù)組a中合并排序基本思想：將待排序元素分成大小大致相同的2個(gè)子集合，改進(jìn)合并排序算法算法mergesort存在遞歸過(guò)程它將序列一分為二，直到序列只剩一個(gè)元素為止，然后不斷合并2個(gè)排好序的序列；改進(jìn)思路：將初始序列看出n個(gè)長(zhǎng)度為1的有序子序列，然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2的有序子序列；再兩兩歸并，重復(fù)直到得到一個(gè)長(zhǎng)度為n的有序序列改進(jìn)合并排序算法算法mergesort存在遞歸過(guò)程改進(jìn)合并排序算法mergesort的遞歸過(guò)程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27

21、76第三步13 27 38 49 65 76 97改進(jìn)合并排序算法mergesort的遞歸過(guò)程可以消去。初始序自然合并排序算法：任何數(shù)組都有現(xiàn)成已排好序的子數(shù)組段，以此為基礎(chǔ)排序4,8,3,7,1,5,6,2先進(jìn)行一次線性掃描，再合并相鄰排好的子數(shù)組段自然合并排序算法：任何數(shù)組都有現(xiàn)成已排好序的子數(shù)組段，以此為快速排序快速排序基本思想：以ap為基準(zhǔn)元素，將數(shù)組ap:r劃分為ap:q-1小, aq和aq+1:r大三段, 然后通過(guò)遞歸調(diào)用分別對(duì)ap:q-1和aq+1:r進(jìn)行快速排序。說(shuō)明：因排序分塊進(jìn)行，合并步驟省略?；舅枷耄阂詀p為基準(zhǔn)元素，將數(shù)組ap:r劃分為atemplate QuickS

22、ort (Type a , int p, int r)if ( p = r ) return;q = Partition (a, p, r);QuickSort (a, p, q-1); /對(duì)左半段排序QuickSort (a, q+1, r); /對(duì)右半段排序template 在Partition (a, p, r)中，記錄的比較和交換是從兩端向中間進(jìn)行的, 值較大的記錄交換到aq+1, r，值較小的記錄交換到ap, q-1。記錄每次移動(dòng)的距離較大，但總的比較和移動(dòng)次數(shù)較少。在Partition (a, p, r)中，記錄的比較和交換prr23p80r14p52例如：ap=52prrrppr

23、r23p80r14p52例如：ap=52prrrptemplate Type Partition (Type a , int p, int r) Type x=ap;while (pr) while (p=x) -r;ap = ar;while (pr & ap=x) +p;ar = ap;ap=x;return p; /返回樞軸所在位置 / Partitiontemplate 基準(zhǔn)元素基準(zhǔn)元素快速排序算法的復(fù)雜性分析快速排序算法的復(fù)雜性分析運(yùn)行時(shí)間與劃分是否對(duì)稱有關(guān)最壞情況：對(duì)于一個(gè)包含n個(gè)元素的數(shù)組，被劃分成兩個(gè)區(qū)域，其中一個(gè)包含n-1個(gè)元素，而另一個(gè)中只有一個(gè)元素。最好情況：每次劃分都產(chǎn)

24、生兩個(gè)大小為n/2的區(qū)域。快速排序算法的復(fù)雜性分析快速排序算法的復(fù)雜性分析 快速排序算法在最好情況下的時(shí)間復(fù)雜性是O(nlogn) 通?；诒容^的排序算法的算法復(fù)雜度是O(n2)快速排序算法因此得名，對(duì)規(guī)模大的問(wèn)題較有效算法設(shè)計(jì)者因?yàn)檫@個(gè)代表性貢獻(xiàn)而獲得1980年的Turing獎(jiǎng) 快速排序算法在最好情況下的時(shí)間復(fù)雜性是O(nlogn)templateint RandomizedPartition (Type a, int p, int r) int i = Random(p,r); Swap(ai, ap); return Partition (a, p, r); 快速排序算法的性能取決于劃分

25、的對(duì)稱性。通過(guò)修改算法partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒(méi)有被劃分時(shí)，可以在ap:r中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對(duì)稱的。最壞時(shí)間復(fù)雜度：O(n2)平均時(shí)間復(fù)雜度：O(nlogn)輔助空間：O(n)或O(logn)template 快速排序算法線性時(shí)間選擇線性時(shí)間選擇線性時(shí)間選擇的基本思想元素選擇問(wèn)題給定線性序集中的n個(gè)元素和一個(gè)整數(shù)k，1kn，要求找出這n個(gè)元素中第k小的元素。當(dāng)k=1時(shí)找最小元素；當(dāng)k=n時(shí)找最大元素；當(dāng)k=(n+1)/2找中位數(shù)算法設(shè)計(jì)思想與快速排序算法的

26、設(shè)計(jì)思想基本相同，即對(duì)輸入數(shù)組進(jìn)行遞歸劃分，但操作上只對(duì)劃分出的兩個(gè)子數(shù)組中的一個(gè)進(jìn)行進(jìn)一步的遞歸處理；線性時(shí)間選擇的基本思想元素選擇問(wèn)題Type RandomizedSelect(Type a, int p, int r, int k) if(p=r) return ap; int i=RandomizedPartition(p,r); / 將數(shù)組劃分為兩部分 int j =i-p+1; /ap:i的元素個(gè)數(shù) if(k=j) return RandomizedSelect(a,p,i,k); else return RandomizedSelect(a,i+1,r,k-j);說(shuō)明：為什么只需

27、要對(duì)其中的一個(gè)子數(shù)組進(jìn)行進(jìn)一步的遞歸處理數(shù)組ap:r被劃分成兩個(gè)子數(shù)組ap:i和ai+1:r,使得ap:i中的元素都不大于ai+1:r中的元素；計(jì)算ap:i中的元素個(gè)數(shù)j，如果kj,則所要找的元素就在ap:i內(nèi)，否則在ai+1:r內(nèi)只要對(duì)其中的一個(gè)子數(shù)組進(jìn)一步的遞歸處理即可Type RandomizedSelect(Type atemplateRandomizedPartition(Type a, int p, int r)int i=rand()%(r-p+1)+p;Swap(ai,ap);return Partition(a,p,r);template Type Partition(Typ

28、e a, int p, int r)int i=p, j=r+1;Type x=ap;while(true)while(a+ix & ix);if(i=j) break;Swap(ai, aj);ap=aj;aj=x;return j;template對(duì)算法的討論RandomizedSelect算法在最壞情況下需要(n2)計(jì)算時(shí)間，其平均計(jì)算時(shí)間為O(n)出發(fā)點(diǎn)：如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)，使得按這個(gè)基準(zhǔn)所劃分出的兩個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組的倍（01），那么就可以在最壞的情況下用O(n)時(shí)間完成選擇任務(wù)對(duì)算法的討論RandomizedSelect算法在最壞情況下說(shuō)明說(shuō)明尋找滿足要求

29、的劃分基準(zhǔn)按以下步驟尋找滿足要求的劃分基準(zhǔn)將n個(gè)輸入元素劃分成n/5個(gè)組，每組5個(gè)元素，只可能有一個(gè)組不是5個(gè)元素。用任意一種排序算法對(duì)每組中的元素進(jìn)行排序，并取出每組中的中位數(shù)，共n/5個(gè)。遞歸調(diào)用算法select來(lái)找這n/5個(gè)元素的中位數(shù)。如果n/5個(gè)為偶數(shù)，就找它的兩個(gè)中位數(shù)中較大的一個(gè)。以這個(gè)元素作為劃分基準(zhǔn)。注：假定n個(gè)元素都互不相等尋找滿足要求的劃分基準(zhǔn)按以下步驟尋找滿足要求的劃分基準(zhǔn)注：假x選擇劃分基準(zhǔn)x選擇劃分基準(zhǔn)分析滿足算法select的要求分析滿足算法select的要求算法復(fù)雜性分析按算法所選基準(zhǔn)x進(jìn)行劃分所得到的2個(gè)子數(shù)組分別至多有3n/4個(gè)元素，無(wú)論對(duì)哪一個(gè)子數(shù)組調(diào)用select都至多用T(3n/4)的時(shí)間找中位數(shù)的中位數(shù)算法復(fù)雜性分析按算法所選基準(zhǔn)x進(jìn)行劃分所得到的2個(gè)子數(shù)組分別分析分析Select算法將每一組的大小定為5，并選取75作為是否進(jìn)行遞歸調(diào)用的分界點(diǎn)。這兩點(diǎn)保證了T(n)的遞歸式中兩個(gè)自變量之和n/5+3n/4=19n/20=an,0a1使T(n)=O(n)的關(guān)鍵*除5和75的組合之外，還有其他選擇分析分析Type Select(Type a , i