算法設(shè)計(jì)及分析 第二章ppt

1、第一章第一章 算法概述算法概述第二章第二章 遞歸與分治策略遞歸與分治策略第三章第三章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃第四章第四章 貪心算法貪心算法第五章第五章 回朔法回朔法第六章第六章 分支限界法分支限界法第七章第七章 概率算法概率算法算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 目錄目錄12算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治2.1 直接或間接地調(diào)用自身的算法稱為遞歸算遞歸算法法。 由分治法產(chǎn)生的子問題往往是原問題的較小模式，為使用遞歸技術(shù)提供了方便。 反復(fù)應(yīng)用分治手段，可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到很容易直接求出其解，自然導(dǎo)致遞歸過程的產(chǎn)生。3算法設(shè)計(jì)與分析算法設(shè)計(jì)與分

2、析 遞歸與分治遞歸與分治當(dāng)子問題足夠大當(dāng)子問題足夠大,需要遞歸求解時(shí)需要遞歸求解時(shí),稱為稱為遞遞歸情況歸情況;當(dāng)子問題足夠小時(shí)當(dāng)子問題足夠小時(shí),不再需要遞歸時(shí)不再需要遞歸時(shí),遞歸遞歸進(jìn)入進(jìn)入“觸底觸底”,進(jìn)入進(jìn)入基本情況基本情況;用函數(shù)自身給出定義的函數(shù)稱為用函數(shù)自身給出定義的函數(shù)稱為遞歸函遞歸函數(shù)數(shù);遞歸式遞歸式是一個(gè)等式或不等式是一個(gè)等式或不等式,它通過更小它通過更小的輸入上的函數(shù)值來描述一個(gè)函數(shù)的輸入上的函數(shù)值來描述一個(gè)函數(shù).4遞歸函數(shù)的內(nèi)部執(zhí)行過程 l（1）運(yùn)行開始時(shí)，為遞歸調(diào)用建立一個(gè)）運(yùn)行開始時(shí)，為遞歸調(diào)用建立一個(gè)工作棧工作棧，其結(jié)構(gòu)包括實(shí)參、局部變量和返回地址；其結(jié)構(gòu)包括實(shí)參、局

3、部變量和返回地址；l（2）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的實(shí)）每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的實(shí)參和局部變量的當(dāng)前值以及調(diào)用后的返回地址參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧壓棧；l（3）每次遞歸調(diào)用結(jié)束后，將棧頂元素）每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧出棧，使相應(yīng)的實(shí)參和局部變量恢復(fù)為調(diào)用前的值，使相應(yīng)的實(shí)參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行位置繼續(xù)執(zhí)行算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治5算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治例例2-3 2-3 Ackerman函數(shù)函數(shù)當(dāng)一個(gè)函數(shù)及它的一個(gè)變量是由函數(shù)自身

4、定義時(shí)，稱這個(gè)函數(shù)是雙遞歸函數(shù)雙遞歸函數(shù)。Ackerman函數(shù)A(n，m)定義如下：1,20) 1), 1(),(2)0 ,(1), 0(2)0 , 1 (mnnmmmnAAmnAnnAmAA該變量是由函數(shù)自身定義6分析分析: :A(n,m)的自變量m的每一個(gè)值都定義了一個(gè)單變量函數(shù)： M=0時(shí)時(shí)， A(n,0)=n+2 M=1時(shí)時(shí) A(1,1)=2 和 A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2， 故A(n,1)=2*n (上式是一個(gè)遞推公式，每當(dāng)n-1便加2） M=2時(shí)，A(1,2)=A(A(0,2),1)=A(1,1)=2 A(n,2)=A(A(n-1,2),1)=2

5、A(n-1,2)， 故A(n,2)= 2n 。 M=3時(shí)，類似的可以推出 M=4時(shí)，A(n,4)的增長速度非?？?，以至于沒有適當(dāng)?shù)臄?shù)學(xué)式子來表示這一函數(shù)。n2222算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治7算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治1、證明、證明 A(1,1)=2因?yàn)橐驗(yàn)閚,m=1使用遞推式（使用遞推式（4） 得得 A(1,1)=A(A(0,1),0)由由A(0,m)=1,故故 A(1,1）=A(1,0)由（由（1）式）式 A(1,0)=2 所以所以A(1,1)=22、證明、證明A(n,1)=2n (n=1)因?yàn)橐驗(yàn)閚, m=1 使用遞歸式使用遞歸式(4) 得

6、得A(n,1)=A(A(n-1,1),0)由公式由公式(3) A(n,1)=A(n-1,1)+2由此式看出由此式看出m=1 時(shí)，時(shí)，n每降一階就增加每降一階就增加2， 一直降到一直降到n=1 即即A(1,1)共增加共增加n個(gè)個(gè)2，n 個(gè)個(gè)2相加和為相加和為2n所以所以A(n,1)=2n8算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治3、證明當(dāng)、證明當(dāng)m=2時(shí)時(shí) A(n,2)=2n由遞推式由遞推式(4) A(n,2)=A(A(n-1,2),1),此時(shí)已經(jīng)演變?yōu)榇藭r(shí)已經(jīng)演變?yōu)閙=1的的情況，式中情況，式中A(n-1,2) 相當(dāng)于相當(dāng)于2節(jié)中的節(jié)中的n的位置，因此利用的位置，因此利用2節(jié)的結(jié)論有

7、節(jié)的結(jié)論有 A(n,2)=2A(n-1,2)可以看出隨著可以看出隨著n的降階會(huì)增長的降階會(huì)增長2的倍數(shù)，那么當(dāng)?shù)谋稊?shù)，那么當(dāng)n降為降為1時(shí)即時(shí)即A(1,2)的情況如何呢？的情況如何呢？根據(jù)遞推式根據(jù)遞推式(4)有有A(1,2)=A(A(0,2),1), 再由公式再由公式(2) A(0,m)=1故故A(1,2)=A(1,1)=2所以所以A(n,2)隨著隨著n的降階每次乘的降階每次乘2，共乘，共乘n次得次得A(n,2)=2n公式得證公式得證 定義單變量的Ackerman函數(shù)A(n)為： A(n)=A(n, n)。 定義其擬逆函數(shù)(n)為： (n)=minkA(k)n。 即(n)是使nA(k)成立的

8、最小的k值。 (n)在復(fù)雜度分析中常遇到。對(duì)于通常所見到的正整數(shù)n，有(n)4。但在理論上(n)沒有上界，隨著n的增加，它以難以想象的慢速度趨慢速度趨向正無窮大。向正無窮大。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治9遞歸樹 T(n) = 3T(n/4) + O(n 2 )算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治10算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治1112補(bǔ)充：主方法（定理） 求解這類遞推式的方法是主方法，主方法依賴于下面的主定理，使用主定理可直接得到遞推式的解。 定理（主定理）： a1且b1是常數(shù)， f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)

9、=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界： （1）若對(duì)于某常數(shù)0，有f(n)=O(nlogba-)，則T(n)=(nlogba)； （2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)； （3）若對(duì)于某常數(shù)0，有f(n)=(nlogba+)，且對(duì)于某個(gè)常數(shù)c 遞歸與分治遞歸與分治13 定理（主定理）： a1且b1是常數(shù)， f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界： （1）若對(duì)于某常數(shù)0，有f(n)=O(nlogba-)，則T(n)=(n

10、logba)； 舉例舉例：T(n) = 16T(n/4) + nT(n) = aT(n/b) + f(n)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治14 定理（主定理）： a1且b1是常數(shù)， f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界： （2）若f(n)=(nlogba)，則T(n)=(nlogbalogn)； 舉例舉例：T(n) = T(3n/7) + 1T(n) = aT(n/b) + f(n)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治15 定理（主定理）： a1且b1是常數(shù)，

11、f(n)是一個(gè)函數(shù)，T(n)由如下的遞推式定義：T(n)=aT(n/b)+f(n)，式中，n/b指n/b或n/b，則T(n)有如下的漸近界： （3）若對(duì)于某常數(shù)0，有f(n)=(nlogba+)，且對(duì)于某個(gè)常數(shù)c 遞歸與分治遞歸與分治優(yōu)點(diǎn)：優(yōu)點(diǎn)：結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易結(jié)構(gòu)清晰，可讀性強(qiáng)，而且容易用數(shù)學(xué)歸納法來證明算法的正確性，因用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。便。缺點(diǎn)：缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多

12、。都比非遞歸算法要多。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治16解決方法：解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法?；癁榉沁f歸算法。1 1、采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)、采用一個(gè)用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，用工作棧。該方法通用性強(qiáng)，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。果不明顯。2 2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。、用遞推來實(shí)現(xiàn)遞歸函數(shù)。3 3、通過、通過變換能變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而將一些遞歸轉(zhuǎn)化為尾

13、遞歸，從而迭代求出結(jié)果。迭代求出結(jié)果。 后兩種方法在時(shí)空復(fù)雜度上均有較大改善，后兩種方法在時(shí)空復(fù)雜度上均有較大改善，但其適用范圍有限。但其適用范圍有限。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治1718尾遞歸是尾遞歸是在遞歸調(diào)用時(shí)“積累”之前調(diào)用的結(jié)果，并將其傳入下一次遞歸調(diào)用中,將遞歸方法中的需要的“所有狀態(tài)”通過方法的參數(shù)傳入下一次調(diào)用中.算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治尾遞歸只會(huì)占用恒量的內(nèi)存,形式上只要最后一個(gè)return語句是單純函數(shù)就可以2.2分治法的基本思想算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治19 將一個(gè)規(guī)模為將一個(gè)規(guī)模為n的問題的問題分解

14、分解為為k個(gè)規(guī)模較小的子問個(gè)規(guī)模較小的子問題，這些子問題題，這些子問題互相獨(dú)立互相獨(dú)立且與且與原問題相同原問題相同。 對(duì)這對(duì)這k個(gè)子問題分別求解個(gè)子問題分別求解。如果子問題的規(guī)模仍。如果子問題的規(guī)模仍然不夠小，則再劃分為然不夠小，則再劃分為k個(gè)子問題，如此遞歸的個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其進(jìn)行下去，直到問題規(guī)模足夠小，很容易求出其解為止。解為止。 將求出的小規(guī)模的問題的解將求出的小規(guī)模的問題的解合并合并為一個(gè)更大規(guī)模為一個(gè)更大規(guī)模的問題的解，的問題的解，自底向上自底向上逐步求出原來問題的解。逐步求出原來問題的解。20 子問題子問題1的規(guī)模是的規(guī)模是n/2 子問

15、題子問題1的解的解 子問題子問題2的解的解 子問題子問題2的規(guī)模是的規(guī)模是n/2 原問題的解原問題的解 原問題原問題的規(guī)模是的規(guī)模是n算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治21算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治問題（問題（N個(gè)輸入）個(gè)輸入）子問題子問題1子問題子問題2子問題子問題K子問題子問題1子問題子問題2子問題子問題k相同類型相同類型合并解合并解 分分治法要求分解成治法要求分解成同類子問題同類子問題，并允許不斷，并允許不斷分解，使問題規(guī)模逐步減小，最終分解，使問題規(guī)模逐步減小，最終可用已知可用已知的方法求解的方法求解足夠小的問題足夠小的問題。22算法設(shè)計(jì)與分析算

16、法設(shè)計(jì)與分析 遞歸與分治遞歸與分治舉例舉例：二路歸并排序二路歸并排序分解過程：分解過程：對(duì)任意長度為對(duì)任意長度為n的序列排序，首先將問的序列排序，首先將問題不斷分解，直至問題可直接求解。題不斷分解，直至問題可直接求解。 長度為長度為n的序列分解為的序列分解為2個(gè)個(gè)n/2的子序列，依次循環(huán)，直的子序列，依次循環(huán)，直至分解為至分解為n個(gè)長度為個(gè)長度為1的序列，顯然長度為的序列，顯然長度為1的序列是的序列是有有序表序表。合并過程：合并過程：將已排序的的子序列不斷合并，形成將已排序的的子序列不斷合并，形成長度為長度為n的排序序列。的排序序列。 然后反復(fù)進(jìn)行兩兩歸并為然后反復(fù)進(jìn)行兩兩歸并為n/2個(gè)有序表

17、；再對(duì)個(gè)有序表；再對(duì)n/2個(gè)有序個(gè)有序表兩兩歸并，循環(huán)直到得到長度為表兩兩歸并，循環(huán)直到得到長度為n的有序線性表。的有序線性表。23算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治template void MergeSort( Type a, int left, int right ) if( leftright ) /至少有2個(gè)元素 int i = ( left + right )/2; /取中點(diǎn) MergeSort( a, left, i ); /對(duì)前半部分排序 MergeSort( a, i+1, right ); /對(duì)后半部分排序 Merge( a, b, left, i, rig

18、ht ); /合并到數(shù)組b Copy( a, b, left, right ); /復(fù)制回?cái)?shù)組a 合并合并步，將有序表步，將有序表aleft,i和和ai+1,right合并到合并到bleft,right問題分解：規(guī)模為問題分解：規(guī)模為原來的一半；問題原來的一半；問題性質(zhì)不變。性質(zhì)不變。24template void MergeSort( Type a, int left, int right ) if( left 遞歸與分治遞歸與分治時(shí)間復(fù)雜度時(shí)間復(fù)雜度T(n)cT(n/2)T(n/2)O(n)O(n)void Merge(Type c, Type d, int i, int m, int r

19、) int la,lb,lc; la=i;lb=m+1;lc=i; while(la=m&lb=n) if(claclb) dlc+=cla+; else dlc+=clb+; while(la=m) dlc+=cla+; while(lb 遞歸與分治遞歸與分治26算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治總結(jié)總結(jié)：分治法的適用條件分治法的適用條件分治法所能解決的問題一般分治法所能解決的問題一般具有以下特征具有以下特征：1. 該該問題規(guī)模問題規(guī)?？s小到一定的程度就可以容易地縮小到一定的程度就可以容易地解決；解決；2. 該問題可以分解為若干個(gè)規(guī)模較小的相同子該問題可以分解為若干個(gè)

20、規(guī)模較小的相同子問題，即該問題具有問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)；3. 利用該問題分解出的子問題的解可以合并為利用該問題分解出的子問題的解可以合并為該問題的解；該問題的解；4. 該問題所分解出的各個(gè)子問題是該問題所分解出的各個(gè)子問題是相互獨(dú)立相互獨(dú)立的，的，即子問題之間不包含公共的子問題即子問題之間不包含公共的子問題。應(yīng)用分治法的前提，它應(yīng)用分治法的前提，它也是大多數(shù)問題可以滿也是大多數(shù)問題可以滿足的，此特征反映了足的，此特征反映了遞遞歸思想歸思想的應(yīng)用。的應(yīng)用。關(guān)鍵特征關(guān)鍵特征，能否利用分治法完，能否利用分治法完全取決于問題是否具有第四條全取決于問題是否具有第四條特征，如果具

21、備了第一條和第特征，如果具備了第一條和第二條特征，而不具備第四條特二條特征，而不具備第四條特征，則可以考慮征，則可以考慮貪心法貪心法或或動(dòng)態(tài)動(dòng)態(tài)規(guī)劃法規(guī)劃法。27算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治分治法的基本步驟分治法的基本步驟: :1. 劃分：劃分：把規(guī)模為把規(guī)模為n的原問題劃分為的原問題劃分為k個(gè)規(guī)個(gè)規(guī)模較小的子問題，并盡量使這模較小的子問題，并盡量使這k個(gè)子問題個(gè)子問題的規(guī)模大致相同。的規(guī)模大致相同。2. 求解子問題：求解子問題：各子問題的解法與原問題各子問題的解法與原問題的解法通常是相同的，可以用的解法通常是相同的，可以用遞歸遞歸的方的方法求解各個(gè)子問題，法求解各個(gè)子問

22、題，有時(shí)也可用有時(shí)也可用循環(huán)來循環(huán)來實(shí)現(xiàn)。實(shí)現(xiàn)。3. 合并：合并：把各個(gè)子問題的解合并把各個(gè)子問題的解合并起來。起來。divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i 遞歸與分治遞歸與分治28 在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同，即，將一個(gè)問題即，將一個(gè)問題分成大小相等的分成大小相等的k個(gè)子問題個(gè)子問題（許多問題取（許多問題取k=2）。）。

23、 使子問題規(guī)模大致相等的做法是出自一種使子問題規(guī)模大致相等的做法是出自一種平衡子問題平衡子問題的的思想，這通常比子問題規(guī)模不等的做法要好。思想，這通常比子問題規(guī)模不等的做法要好。|P|問題問題P的規(guī)模的規(guī)模n0為閥值為閥值adhoc(P)基本子算法基本子算法29分治法的復(fù)雜性分析 從一般設(shè)計(jì)模式看，用分治法設(shè)計(jì)的程序通常是一個(gè)遞歸算法。 分治法將規(guī)模為n的問題分成k k個(gè)規(guī)模為個(gè)規(guī)模為n/mn/m的子問題的子問題： 設(shè)n0=1,且adhoc解問題耗費(fèi)1 1個(gè)單位時(shí)間個(gè)單位時(shí)間。 再設(shè)將原問題分解為k個(gè)子問題以及用merge將k個(gè)子問題的解合并為原問題的解需用f (n)個(gè)單位時(shí)間個(gè)單位時(shí)間。用用

24、T(n)（遞歸方程）表示（遞歸方程）表示該分治法求解規(guī)模為該分治法求解規(guī)模為|P|=n的問題所需的計(jì)算時(shí)間：的問題所需的計(jì)算時(shí)間：11)()/()1()( nnnfmnkTOnT算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治3011)()/()1()( nnnfmnkTOnT通過迭代法求得方程解：通過迭代法求得方程解： 1log0log)/()(nmjjjkmmnfknnT基本子問題基本子問題花費(fèi)時(shí)間花費(fèi)時(shí)間合并步花費(fèi)合并步花費(fèi)時(shí)間時(shí)間 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治312.3 二分搜索技術(shù)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治 問題描述：問題描述：已知一個(gè)

25、按非降次序排列的元素表a1,a2,an，判定某個(gè)給定元素x是否在該表中出現(xiàn)，若是，則找出該元素在表中的位置，并置于j，否則，置j為0。 一般解決方法：一般解決方法：從頭到尾查找一遍。a1a2a3a4anx成功與不成功的最壞情況下需成功與不成功的最壞情況下需O(n)次比較次比較分析：如果n=1即只有一個(gè)元素，則只要比較這個(gè)元素和x就可以確定x是否在表中。因此這個(gè)問題滿足分治法的第一個(gè)適用條件分析：比較x和a的中間元素amid，若x=amid，則x在L中的位置就是mid；如果xai，同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x，其方法都和在a中查找x一樣，只不過是查找的規(guī)?？s

26、小了。這就說明了此問題滿足分治法的第二個(gè)和第三個(gè)適用條件。 分析：很顯然此問題分解出的子問題相互獨(dú)立，即在ai的前面或后面查找x是獨(dú)立的子問題，因此滿足分治法的適用條件。分析：分析：該問題的規(guī)模縮小到一定的程度就可以容易地該問題的規(guī)?？s小到一定的程度就可以容易地解決；解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題該問題可以分解為若干個(gè)規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解；分解出的子問題的解可以合并為原問題的解；分解出的各個(gè)子問題是相互獨(dú)立的。分解出的各個(gè)子問題是相互獨(dú)立的。 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治32二分搜索算法二分搜索算法：template

27、int BinarySearch(Type a, const Type& x, int l, int r) while (r = l) int m = (l+r)/2; if (x = am) return m; if (x 遞歸與分治遞歸與分治332.8 快速排序算法思路 對(duì)Ap:r,按以下步驟進(jìn)行排序按以下步驟進(jìn)行排序：(1)分解分解: 取取A中一元素為支點(diǎn)中一元素為支點(diǎn), 將將Ap:r分成分成3段段: Ap:q-1, Aq, A q+1:r, 其中其中l(wèi) A p:q-1中元素中元素 Aq, l Aq+1: r中元素中元素 Aq; (2)求解求解:通過遞歸調(diào)用分別對(duì)通過遞歸調(diào)用分別

28、對(duì)Ap:q-1和和Aq+1:r 排排序。序。(3)合并合并: 合并合并A p:q-1, Aq , A q+1:r 為為Ap:r。34算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治 快速排序快速排序 得得: T: Tmaxmax (n)=O(n (n)=O(n2 2) ) 快速排序算法快速排序算法 template void QuickSoft(T a , int p, int r) if(pr) int q=Partition(a, p, r) QuickSort(a, p, q-1); /對(duì)左半段排序 QuickSoft(a, q+1, r); /對(duì)右半段排序 template int

29、Partion(T a ,int p, int r ) int i=p; j=r+1; t x=ap； /取支點(diǎn) /將x的元素交換到左邊 /將x的元素交換到右邊 while (true) while(a+i x)； if (i=j ) break; swap(ai,aj); ap = aj； aj = x; return j T Tminmin(n)= (n)= O(1) n=1O(1) n12T(n/2)+O(n) n1 得得: T: Tminmin (n)=O(nlogn) (n)=O(nlogn) 復(fù)雜性分析 T Tmaxmax(n)= (n)= O(1) n=1O(1) n1T(n-1

30、)+O(n) n135隨機(jī)選擇支點(diǎn)的快速排序 template void randomizedQuickSoft(T a, int p, int r) if (p 遞歸與分治遞歸與分治 快速排序快速排序 template int randomizedPartition(T a, int p, int r) int i=random( p, r) swap( ai, ap ) return Partition (a,p,r)36快速排序算法性能取決于劃分的對(duì)稱性2.9 線性時(shí)間選擇線性時(shí)間選擇問題陳述 求求n個(gè)元素中的第個(gè)元素中的第k小元素小元素.給定線性序集中n個(gè)不同的元素和一個(gè)整數(shù)k，1 k

31、 n要求找出這n個(gè)元素中第k小的元素，即如果將這n個(gè)元素依其線性序排列時(shí)，排在第k個(gè)位置的元素即為我們要找的元素。當(dāng)當(dāng)k=1時(shí)時(shí),找最小元找最小元;當(dāng)當(dāng)k=n時(shí)時(shí),找最大元素找最大元素;當(dāng)當(dāng)k=(n+1)/2時(shí)時(shí),找中位數(shù)找中位數(shù).37算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治38算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治算法思路 模仿快速排序模仿快速排序,對(duì)輸入數(shù)組對(duì)輸入數(shù)組A進(jìn)行二分進(jìn)行二分,使使子數(shù)組子數(shù)組A1的元素的元素 A2中的元素中的元素,分點(diǎn)分點(diǎn)J由隨機(jī)數(shù)產(chǎn)生由隨機(jī)數(shù)產(chǎn)生.若若K J,則則K為為A1的第的第K小元小元, 若若KJ,則則K為為A2的第的第 K-J小元

32、小元.39算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治找數(shù)組a0:n-1第k小元素調(diào)用RandomizedSelect(a,0,n-1,k)template T RandomizedSelect (a , int p, int r, int k) if (p=r) return ap; int i = RandomizedPartition(a, p, r); j=i-p+1; /支點(diǎn)元素是第支點(diǎn)元素是第j小個(gè)元素小個(gè)元素,左半部元素個(gè)數(shù)左半部元素個(gè)數(shù) if k=j return Ai; if ( k j ) return RandomizedSelect(a, p, i-1, k);

33、else return RandomizedSelect(a, i +1, r, k - j); p,r 數(shù)組范圍K:第k小個(gè)元素與快速排序與快速排序算法不同算法不同,它它只對(duì)子數(shù)組只對(duì)子數(shù)組之一之一進(jìn)行遞進(jìn)行遞歸歸處理。處理。40 執(zhí)行執(zhí)行RandomizedPartiton，數(shù)組，數(shù)組ap:r劃分成兩個(gè)子劃分成兩個(gè)子數(shù)組數(shù)組ap:i和和ai+1:r，其中，其中ap:i元素元素ai+1:r元素元素 計(jì)算子數(shù)組計(jì)算子數(shù)組ap:i中元素個(gè)數(shù)中元素個(gè)數(shù)j如果如果kj,則要找的第則要找的第k小元素落在子數(shù)組小元素落在子數(shù)組ai+1:r中中,要要找的找的ap:r中第中第k小的元素是小的元素是ai+1:

34、r中的第中的第k-j小小的元素。的元素。如果如果k=j,找到第找到第k小個(gè)元素，返回小個(gè)元素，返回ai遞歸循環(huán)。遞歸循環(huán)。算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治41 T Tminmin(n)= (n)= d d T(n)=T(n/2)+cn T(n)=T(n/2)+cn 分析分析 最壞情況最壞情況: T: Tmaxmax(n)=(n)= (n2 ) (左半總為空左半總為空) (等分點(diǎn)等分點(diǎn)) 得得: T: Tminmin (n)= (n)= (n) (n) 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治最壞情況下的選擇最壞情況下的選擇算法分析算法分析42算法設(shè)計(jì)與分析算法設(shè)計(jì)與

35、分析 遞歸與分治遞歸與分治算法算法RandomizedSelectRandomizedSelect需要需要(n(n) )計(jì)算時(shí)間。計(jì)算時(shí)間。例如在找最小元素時(shí)，總是在最大元素處劃分。例如在找最小元素時(shí)，總是在最大元素處劃分。(n-1)+(n-2)+1=n(n-1)+(n-2)+1=n算法算法RandomizedSelectRandomizedSelect不穩(wěn)定的不穩(wěn)定的原因：原因：由于隨機(jī)劃分由于隨機(jī)劃分函數(shù)使用函數(shù)使用了一個(gè)隨機(jī)數(shù)產(chǎn)生器了一個(gè)隨機(jī)數(shù)產(chǎn)生器RandomRandom, , 產(chǎn)生產(chǎn)生p p和和r r之間的一個(gè)隨機(jī)整數(shù)，之間的一個(gè)隨機(jī)整數(shù)，因此因此產(chǎn)生產(chǎn)生的劃分基準(zhǔn)是隨機(jī)的。的劃分基

36、準(zhǔn)是隨機(jī)的?？梢宰C明，可以證明，算法可以算法可以在在O(n)O(n)平均時(shí)間內(nèi)找平均時(shí)間內(nèi)找出出n n個(gè)輸入元素中的第個(gè)輸入元素中的第k k小元素。小元素。43算法思路(中間的中間):將將A中元素分為中元素分為n/r組組,除最后一組外除最后一組外,每組元素為每組元素為r個(gè)個(gè),用任意排序算法排序用任意排序算法排序,取出每組的中位數(shù)取出每組的中位數(shù),對(duì)對(duì)n/r個(gè)中位數(shù)遞歸調(diào)用個(gè)中位數(shù)遞歸調(diào)用,找到中位數(shù)找到中位數(shù),以該元素作為劃分基準(zhǔn)以該元素作為劃分基準(zhǔn).算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治xtemplateT Select(T a, int p, int r, int k ) if

37、 (r-p75) 用簡單排序法排序； return ap+k-1 ； for(int i=0 ;i=(r-p-4)/5 ; i+) 將ap+5*i至ap+5*i-4的第3小元素與ap+i交換位置； /找中位數(shù)的中位數(shù) T x=Select(a, p, p+(r-p-4)/5, (r-p-4)/10); int i=Partition(a,p,r,x), j=i-p+1; if (k=j) return Select(a,p,i,k) else return Select(a,i+1,r,k-j) 最壞情況下的選擇算法:算法分析 T(n)= T(n)= 得得: T(n)=O(n) : T(n)=

38、O(n) c c1 1 n75n75時(shí)時(shí), max |left|,|right| 遞歸與分治遞歸與分治 一般方法：一般方法： O(n2) 效率太低！效率太低！ 分治法：分治法：bdbcadacXYdcYbaXnnnn 2222)(222 復(fù)雜性分析：復(fù)雜性分析： 12/411nnOnTnOnT n/2n/2位位 n/2n/2位位 n/2n/2位位 n/2n/2位位X=X=Y=Y=ABCDT(n)=O(n2) 沒有改進(jìn)沒有改進(jìn)46分析分析這兩個(gè)算式更復(fù)雜一些，但它們僅需要這兩個(gè)算式更復(fù)雜一些，但它們僅需要3次次n/2位乘法。位乘法。ac、bd和和(ab)(dc)算法改進(jìn)算法設(shè)計(jì)與分析算法設(shè)計(jì)與分

39、析 遞歸與分治遞歸與分治 為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。為此，把XY寫成另外的形式：XY = ac2n + (a-b)(d-c)+ac+bd) 2n/2 + bd 或或XY = ac2n + (a+b)(c+d)-ac-bd) 2n/2 + bd 12/311nnOnTnOnT結(jié)論：結(jié)論：T(n)=O(nlog3) =O(n1.59) 較大的改進(jìn)較大的改進(jìn) S=SIGN(X)*SIGN(Y)； X:=ABS(X)；Y:=ABS(Y)； if n=l then if (X=1) and (Y=1) then return(S) else return(0) else A:=X的左邊n/

40、2位； B:=X的右邊n/2位； C:=Y的左邊n/2位； D:=Y的右邊n/2位； m1:=MULT(A，C，n/2)； m2:=MULT(A-B,D-C，n/2)； m3:=MULT(B，D，n/2)； S:=S*(m1*2n+(m1+m2+m3)*2n/2+m3)； return (S) X,YX,Y為為2 2個(gè)小于個(gè)小于2 2n n的二進(jìn)制整數(shù)，的二進(jìn)制整數(shù)，S=XYS=XYfunction MULT(X,Y,n)大數(shù)相乘的分治遞歸算法大數(shù)相乘的分治遞歸算法二進(jìn)制大整數(shù)二進(jìn)制大整數(shù)乘法同樣可應(yīng)乘法同樣可應(yīng)用于十進(jìn)制大用于十進(jìn)制大整數(shù)的乘法整數(shù)的乘法.存放存放XY的符號(hào)的符號(hào)存放三個(gè)乘積

41、存放三個(gè)乘積算法算法472.5 Strassen矩陣相乘法矩陣相乘法常規(guī)算法 設(shè)矩陣設(shè)矩陣A=(aij)n n, B=(bij)n n, C=A B=(cij)n n 計(jì)算C共需nn2個(gè)乘法, n2(n-1)個(gè)加法. T(n)=O(nT(n)=O(n3 3) ) 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治48 nkkjikijbac1 如果依此定義來計(jì)算矩陣如果依此定義來計(jì)算矩陣A和和B的乘積矩陣的乘積矩陣C，則，則每計(jì)算每計(jì)算C的一個(gè)元素的一個(gè)元素Ci,j，需要做，需要做n次乘法和次乘法和n-1次次加法。加法。49算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治C11=A11B11

42、+A12B21 C12=A11B12+A12B22C21=A21B11+A22B21 C22=A21B12+A22B22 首先假定n是2（n=2k）的冪，如果相乘的兩矩陣A和B不是方陣，可以通過適當(dāng)添加全零行和全零列，使之成為行列數(shù)為2的冪的方陣。 使用分治法，將矩陣A、B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣，每個(gè)子矩陣都是n/2n/2的方陣 。由此可將方程C=AB重寫為： 222112112221121122211211BBBBAAAACCCC算法思路 50算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治 如果n=2，則兩個(gè)2階方陣的乘積可以直接計(jì)算出來，共需8次乘法和4次加法。 當(dāng)

43、子矩陣的階大于2時(shí)，可以繼續(xù)將子矩陣分塊，直到子矩陣的階降為2。這樣，就產(chǎn)生了一個(gè)分治降階的遞歸算法分治降階的遞歸算法。依此算法，計(jì)算2個(gè)n階方陣的乘積轉(zhuǎn)化為計(jì)算8個(gè)n/2階方陣的乘積和4個(gè)n/2階方陣的加法。2個(gè)n/2n/2矩陣的加法顯然可以在c*n2/4(O(n2) 時(shí)間內(nèi)完成，這里c是一個(gè)常數(shù)。 上述分治法的計(jì)算時(shí)間耗費(fèi)T(n)的遞歸方程滿足： 22/8212nnOnTnOnTT(n)=O(n3) 沒有改進(jìn)，原因是沒有減少矩陣乘法沒有改進(jìn)，原因是沒有減少矩陣乘法次數(shù)。次數(shù)。51算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治為了降低時(shí)間復(fù)雜度，必須減少乘法次數(shù)，其關(guān)鍵在于計(jì)為了降低時(shí)間

44、復(fù)雜度，必須減少乘法次數(shù)，其關(guān)鍵在于計(jì)算算2個(gè)個(gè)2階方陣的乘積時(shí)所用乘法次數(shù)能否少于階方陣的乘積時(shí)所用乘法次數(shù)能否少于8次。為此，次。為此，Strassen提出了一種只用提出了一種只用7次乘法運(yùn)算次乘法運(yùn)算計(jì)算計(jì)算2階方陣乘積的方法階方陣乘積的方法（但增加了加（但增加了加/減法次數(shù)）：減法次數(shù)）：M1=A11(B12-B22)， M2=(A11+A12)B22 M3=(A21+A22)B11， M4=A22(B21-B11) M5=(A11+A22)(B11+B22)， M6=(A12-A22)(B21+B22) M7=(A11-A21)(B11+B12)731543216245MMMMMMM

45、MMMMMC11 =M5+ M4 - M2+M6C12 = M1+M2C21 = M3+M4C22 = M5+M1 - M3 - M7算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治 得得: T(n)=O(n: T(n)=O(nlog7log7) ) =O(n =O(n2.812.81) ) 分析 52做了這做了這7次乘法后，再做若干次加次乘法后，再做若干次加/減法就可以得到：減法就可以得到： 22/7212nnOnTnOnT 較大的改進(jìn)較大的改進(jìn)procedure STRASSEN(n, A, B, C)； if n=2 then MATRIX_MULTIPLY(A, B, C) else

46、 將矩陣將矩陣A A和和B B分塊；分塊； STRASSEN( n/2，A11，B12-B22，M1)； STRASSEN( h/2，A11+A12，B22，M2)； STRASSEN( n/2，A21+A22，B11，M3)； STRASSEN( n/2，A22，B21-B11，M4)； STRASSEN( n/2，A11+A22，B11+B22，M5) STRASSEN( n/2，A12-A22，B21+B22，M6)； STRASSEN( n/2，A11+A21，B11+B12，M7)731543216245MMMMMMMMMMMMC:=矩陣相乘矩陣相乘 Strassen 算法算法算法算

47、法算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治53問題陳述在一個(gè)在一個(gè)2k 2k個(gè)方格組成的棋盤中個(gè)方格組成的棋盤中,恰有一方恰有一方格殘缺格殘缺, 殘缺方格的位置有殘缺方格的位置有22k種。故對(duì)任何種。故對(duì)任何k0,殘缺棋殘缺棋盤有盤有22k種種. 要求用要求用L型骨牌覆蓋殘缺棋盤上的所有方格型骨牌覆蓋殘缺棋盤上的所有方格且任何且任何2個(gè)個(gè)L型骨牌不得重疊覆蓋。型骨牌不得重疊覆蓋。2.6 6 棋盤覆蓋棋盤覆蓋算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治54552k 2k 的棋盤覆蓋中，用到的骨牌數(shù)為的棋盤覆蓋中，用到的骨牌數(shù)為(4k- -1)/3算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸

48、與分治遞歸與分治 算法思路 當(dāng)當(dāng)k0時(shí)時(shí),將將2k 2k棋盤分割為棋盤分割為4個(gè)個(gè)2k-1 2k-1子子棋盤棋盤,殘缺方格必位于殘缺方格必位于4個(gè)子棋盤之一個(gè)子棋盤之一.其余其余3個(gè)子棋盤中個(gè)子棋盤中無殘缺方格無殘缺方格. 用一個(gè)用一個(gè)L型骨牌覆蓋這型骨牌覆蓋這3個(gè)較小棋盤的結(jié)合處個(gè)較小棋盤的結(jié)合處.這這3個(gè)個(gè)子子棋盤上被棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的殘缺型骨牌覆蓋的方格就成為該棋盤上的殘缺方格方格,原問題轉(zhuǎn)化為原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸個(gè)較小規(guī)模的棋盤覆蓋問題。遞歸地使用這種分割，直至棋盤簡化為地使用這種分割，直至棋盤簡化為1 1棋盤棋盤.算法設(shè)計(jì)與分析算法設(shè)計(jì)

49、與分析 遞歸與分治遞歸與分治為此將剩余為此將剩余3棋盤轉(zhuǎn)化為殘缺棋盤棋盤轉(zhuǎn)化為殘缺棋盤: 56算法分析 設(shè)設(shè)T(k)T(k)為為覆蓋覆蓋2k 2k殘缺棋盤殘缺棋盤的時(shí)間的時(shí)間, , 當(dāng)當(dāng)k=0時(shí)覆蓋它需要常數(shù)時(shí)間時(shí)覆蓋它需要常數(shù)時(shí)間O(1).當(dāng)當(dāng)k0時(shí)時(shí),測(cè)試哪個(gè)子棋盤殘缺以及形成測(cè)試哪個(gè)子棋盤殘缺以及形成3個(gè)殘缺子個(gè)殘缺子棋盤需要棋盤需要O(1),覆蓋覆蓋4個(gè)殘缺子棋盤需四次遞歸調(diào)用個(gè)殘缺子棋盤需四次遞歸調(diào)用,共需時(shí)間共需時(shí)間4T(k-1)T(k-1) . T(k)= T(k)= O(1)4T(k-1)+ 4T(k-1)+ O(1) 迭代法解得迭代法解得: T(k)=: T(k)= (4(4

50、k k) )與所需骨與所需骨牌數(shù)同階牌數(shù)同階算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治57void ChessBoard(int tr, int tc, int dr, int dc, int size)void ChessBoard(int tr, int tc, int dr, int dc, int size) if (size=1) return if (size=1) return； int t=tile+int t=tile+，/ / L L型骨牌數(shù)型骨牌數(shù) s=sizes=size2 2； / / 分割棋盤分割棋盤 / /覆蓋左上角子棋盤覆蓋左上角子棋盤 if (dr t

51、r +s & dc tc +S)if (dr tr +s & dc 遞歸與分治遞歸與分治tr:左上角方格行左上角方格行tc:左上角方格列左上角方格列dr:殘缺方格行殘缺方格行dc:殘缺方格列殘缺方格列size:棋盤行數(shù)棋盤行數(shù)Board:為全局變量為全局變量二維數(shù)組表示棋盤二維數(shù)組表示棋盤58 /覆蓋右上角子棋盤覆蓋右上角子棋盤 if (dr = tc +S) /特殊方格在此棋盤中特殊方格在此棋盤中 ChessBoard (tr，tc +s ，dr，dc，S)； else / /此棋盤中無特殊方格此棋盤中無特殊方格 / /用用t t號(hào)骨牌覆蓋左下角號(hào)骨牌覆蓋左下角 Boardt

52、r+s-1tc+s=t； / /覆蓋其余方格覆蓋其余方格 Chessboard(tr，tc+s，tr+s-1，tc+s，s)； . void outputBoard( int size) for int i=0 ;isize ;i+) for int j=0 ;jsize ;j+)； coutsetw(5)board ij; cout 遞歸與分治遞歸與分治5960算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治 給定平面給定平面S上上n個(gè)點(diǎn)個(gè)點(diǎn),找其中的一對(duì)點(diǎn)找其中的一對(duì)點(diǎn),使得在使得在 n(n-1)/2 個(gè)點(diǎn)對(duì)中個(gè)點(diǎn)對(duì)中, 該點(diǎn)對(duì)的距離最小。該點(diǎn)對(duì)的距離最小。2.10 最接近點(diǎn)對(duì)問題問題描

53、述u簡化問題（一維問題）u為了使問題易于理解和分析，先來考慮一一維的情形。此時(shí)，S中的n個(gè)點(diǎn)退化為x軸上的n個(gè)實(shí)數(shù) x1,x2,xn。最接近點(diǎn)對(duì)即為這n個(gè)實(shí)數(shù)中相差最小的2個(gè)實(shí)數(shù)。61算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治假設(shè)我們用x軸上某個(gè)點(diǎn)m將S劃分為2個(gè)子集S1和S2 ，基于平衡子問題平衡子問題的思想，用S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。遞歸地在S1和S2上找出其最接近點(diǎn)對(duì)p1,p2和q1,q2，并設(shè)d=min|p1-p2|,|q1-q2|，S中的最接近點(diǎn)對(duì)或者是p1,p2，或者是q1,q2，或者是某個(gè)p3,q3，其中p3S1且q3S2。能否在線性時(shí)間內(nèi)找到能否在線性時(shí)間內(nèi)找到p3,q3？62算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治u如果S的最接近點(diǎn)對(duì)是p3,q3，即|p3-q3| 遞歸與分治遞歸與分治Bool Cpairl(S,d) n=|S|; if (n 遞歸與分治遞歸與分治算法思路64u二維平面的情況：二維平面的情況： p1p2 l算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 遞歸與分治遞歸與分治