遞歸與分治策略_第1頁
遞歸與分治策略_第2頁
遞歸與分治策略_第3頁
遞歸與分治策略_第4頁
遞歸與分治策略_第5頁
已閱讀5頁,還剩33頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、遞歸與分治策略第1頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三 學(xué)習(xí)要點(diǎn):理解遞歸的概念。掌握設(shè)計(jì)有效算法的分治策略。通過下面的范例學(xué)習(xí)分治策略設(shè)計(jì)技巧。 (1)二分搜索技術(shù); (2)合并排序和快速排序; 主要內(nèi)容:2.0 分治法總體思想2.1 遞歸:階乘、 Fibonacci和Hanoi2.2 分治法的適用條件, 基本步驟,復(fù)雜性分析2.3 二分搜索技術(shù)2.4 快速排序2.5 合并排序總結(jié)第2頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三 將要求解的較大規(guī)模的問題分割成k個更小規(guī)模的子問題。2.0 分治法總體思想nT(n/2)T(n/2)T(n/2)T(n/2)T(

2、n)= 對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小,則再劃分為k個子問題,如此遞歸的進(jìn)行下去,直到問題規(guī)模足夠小,很容易求出其解為止。第3頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.0 算法總體思想對這k個子問題分別求解。如果子問題的規(guī)模仍然不夠小,則再劃分為k個子問題,如此遞歸的進(jìn)行下去,直到問題規(guī)模足夠小,很容易求出其解為止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 將求出的小規(guī)

3、模的問題的解合并為一個更大規(guī)模的問題的解,自底向上逐步求出原來問題的解。第4頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.0 算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解,自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)第5頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.0 算法總體思想將求出的小規(guī)模的問題的解合并為一個更大規(guī)模的問題的解

4、,自底向上逐步求出原來問題的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) 分治法的設(shè)計(jì)思想是,將一個難以直接解決的大問題,分割成一些規(guī)模較小的相同問題,以便各個擊破,分而治之。第6頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.1 遞歸的概念直接或間接地調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。由分治法產(chǎn)生的子問題往往是原問題的較小模式,這就為使用遞歸技術(shù)提供了方便。在這

5、種情況下,反復(fù)應(yīng)用分治手段,可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小,最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟,經(jīng)常同時應(yīng)用在算法設(shè)計(jì)之中,并由此產(chǎn)生許多高效算法。下面來看幾個實(shí)例。第7頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.1 遞歸的概念例1 階乘函數(shù) 階乘函數(shù)可遞歸地定義為:邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個要素,遞歸函數(shù)只有具備了這兩個要素,才能在有限次計(jì)算后得出結(jié)果。第8頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.1 遞歸的概念例2 Fibonacci數(shù)列無窮數(shù)列1,1,2,3

6、,5,8,13,21,34,55,稱為Fibonacci數(shù)列。它可以遞歸地定義為:邊界條件遞歸方程第n個Fibonacci數(shù)可遞歸地計(jì)算如下:int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); 第9頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三例2 Fibonacci調(diào)用結(jié)構(gòu):第10頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三例2 Fib復(fù)雜度分析: The call tree is a full binary tree down to depth n/2, t

7、he rightmost path being the shortest, such as n,n-2,0. (n is even). Therefore, the running time is at least O(2n/2)第11頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三Modify the procedure of Example 2, whichcomputes Fibonacci numbers, to use only aconstant numbers for work space and still computeFn in O(n) time.if (n =

8、1) return n;prev2 = 0; prev1 = 1;for (i = 2; i 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 第14頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.1 遞歸小結(jié)優(yōu)點(diǎn):結(jié)構(gòu)清晰,可讀性強(qiáng),而且容易用數(shù)學(xué)歸納法來證明算法的正確性,因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大方便。缺點(diǎn):遞歸算法的運(yùn)行效率較低,無論是耗費(fèi)的計(jì)算時間還是占用的存儲空間都比非遞歸算法要多。第15頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三解決方法:在遞歸算法中消除遞歸調(diào)用,使其轉(zhuǎn)化為非遞歸算法

9、。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強(qiáng),但本質(zhì)上還是遞歸,只不過人工做了本來由編譯器做的事情,優(yōu)化效果不明顯。2、用遞推來實(shí)現(xiàn)遞歸函數(shù)。反向遞歸3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸,從而迭代求出結(jié)果。反演變換 后兩種方法在時空復(fù)雜度上均有較大改善,但其適用范圍有限。2.1 遞歸小結(jié)第16頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.2 分治法的適用條件分治法所能解決的問題一般具有以下幾個特征:該問題的規(guī)??s小到一定的程度就可以容易地解決;該問題可以分解為若干個規(guī)模較小的相同問題,即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題

10、的解;該問題所分解出的各個子問題是相互獨(dú)立的,即子問題之間不包含公共的子問題。 因?yàn)閱栴}的計(jì)算復(fù)雜性一般是隨著問題規(guī)模的增加而增加,因此大部分問題滿足這個特征。這條特征是應(yīng)用分治法的前提,它也是大多數(shù)問題可以滿足的,此特征反映了遞歸思想的應(yīng)用能否利用分治法完全取決于問題是否具有這條特征,如果具備了前兩條特征,而不具備第三條特征,則可以考慮貪心算法或動態(tài)規(guī)劃。這條特征涉及到分治法的效率,如果各子問題是不獨(dú)立的,則分治法要做許多不必要的工作,重復(fù)地解公共的子問題,此時雖然也可用分治法,但一般用動態(tài)規(guī)劃較好。第17頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三divide-and-con

11、quer(P) if ( | P | = n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk;/分解問題 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 2.2 分治法的基本步驟人們從大量實(shí)踐中發(fā)現(xiàn),在用分治法設(shè)計(jì)算法時,最好使子問題的規(guī)模大致相同。即將一個問題分成大小相等的k個子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancin

12、g)子問題的思想,它幾乎總是比子問題規(guī)模不等的做法要好。第18頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.2 分治法的復(fù)雜性分析一個分治法將規(guī)模為n的問題分成k個規(guī)模為nm的子問題去解。設(shè)分解閥值n0=1,且adhoc解規(guī)模為1的問題耗費(fèi)1個單位時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規(guī)模為|P|=n的問題所需的計(jì)算時間,則有:通過迭代法求得方程的解:注意:遞歸方程及其解只給出n等于m的方冪時T(n)的值,但是如果認(rèn)為T(n)足夠平滑,那么由n等于m的方冪時T(n)的值可以估計(jì)T(n)的

13、增長速度。通常假定T(n)是單調(diào)上升的,從而當(dāng)minmi+1時,T(mi)T(n)T(mi+1)。 第19頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三分析:如果n=1即只有一個元素,則只要比較這個元素和x就可以確定x是否在表中。因此這個問題滿足分治法的第一個適用條件分析:比較x和a的中間元素amid,若x=amid,則x在L中的位置就是mid;如果xai,同理我們只要在amid的后面查找x即可。無論是在前面還是后面查找x,其方法都和在a中查找x一樣,只不過是查找的規(guī)??s小了。這就說明了此問題滿足分治法的第二個和第三個適用條件。 分析:很顯然此問題分解出的子問題相互獨(dú)立,即在ai的

14、前面或后面查找x是獨(dú)立的子問題,因此滿足分治法的第四個適用條件。2.3 二分搜索技術(shù)給定已按升序排好序的n個元素a0:n-1,現(xiàn)要在這n個元素中找出一特定元素x。分析:該問題的規(guī)??s小到一定的程度就可以容易地解決;該問題可以分解為若干個規(guī)模較小的相同問題;分解出的子問題的解可以合并為原問題的解;分解出的各個子問題是相互獨(dú)立的。 第20頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.3 二分搜索技術(shù)給定已按升序排好序的n個元素a0:n-1,現(xiàn)要在這n個元素中找出一特定元素x。據(jù)此容易設(shè)計(jì)出二分搜索算法:template int BinarySearch(Type a, const

15、Type& 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) 時間,因此整個算法在最壞情況下的計(jì)算時間復(fù)雜性為O(logn) 。第21頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 QuicksortQuicksort Strategy:

16、通過一趟排序?qū)⒋判蛴涗浄指畛瑟?dú)立的兩部分,其中一部分的關(guān)鍵字均比另一部分的關(guān)鍵字小,然后分別對這兩部分記錄遞歸地繼續(xù)分別進(jìn)行排序,以達(dá)到整個序列有序。 C.A.R. Hoare (Tony Hoare)教授,1980年獲得美國計(jì)算機(jī)學(xué)會(ACM)設(shè)立的計(jì)算機(jī)界最高獎圖靈獎 第22頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 快速排序在快速排序中,記錄的比較和交換是從兩端向中間進(jìn)行的,關(guān)鍵字較大的記錄一次就能交換到后面單元,關(guān)鍵字較小的記錄一次就能交換到前面單元,記錄每次移動的距離較大,因而總的比較和移動次數(shù)較少。templatevoid QuickSort (Type a

17、, int p, int r) if (pr) int q=Partition(a,p,r); QuickSort (a,p,q-1); /對左半段排序 QuickSort (a,q+1,r); /對右半段排序 第23頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三templateint Partition (Type a, int p, int r) int i = p+1, j = r; Type x=ap; / 將 x的元素交換到右邊區(qū)域 while (true) while (ai x)j-; if (i = j) break; Swap(ai, aj) i+;j-; ap

18、= aj; aj = x; return j; 2.4 快速排序: Partition方法1正確嗎?第24頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 一趟快速排序的算法是: Partition方法21)設(shè)置兩個變量I、J,排序開始的時候:I=0,J=N-1; 2)以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù),賦值給key,即 key=A0; 3)從J開始向前搜索,即由后開始向前搜索(J=J-1),找到第一個小于key的值A(chǔ)J,并與AI交換; 4)從I開始向后搜索,即由前開始向后搜索(I=I+1),找到第一個大于key的AI,與AJ交換; 5)重復(fù)第3、4、5步,直到 I=J; (3,4步

19、是在程序中沒找到時候j=j-1,i=i+1。找到并交換的時候i, j指針位置不變。另外當(dāng)i=j這過程一定正好是i+或j+完成的最后另循環(huán)結(jié)束) 第25頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 Quicksort: example初始關(guān)鍵字:49,38,65,97,76,13,27,49pivot key 49jji1次交換后:27,38,65,97,76,13, ,49iji2次交換后:27,38, ,97,76,13,65,49ijj3次交換后:27,38,13,97,76, ,65,49iji4次交換后:27,38,13, ,76,97,65,49jij一趟完成后:

20、27,38,13,49,76,97,65,49第26頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 Analysis of Quicksort: worst case情況:劃分后產(chǎn)生的兩區(qū)域分別包含n-1和1個元素第27頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 Analysis of Quicksort: average behavior 方法1第28頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.4 Analysis of Quicksort: average behavior:方法1第29頁,共38頁,2022年,5月20日,19點(diǎn)3

21、6分,星期三2.4 Analysis of Quicksort: average behavior 方法2可得其解:T(n)=O(nlogn)第30頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.5 合并排序基本思想:將待排序元素分成大小大致相同的2個子集合,分別對2個子集合進(jìn)行排序,最終將排好序的子集合合并成為所要求的排好序的集合。 void MergeSort(Type a, int left, int right) if (leftright) /至少有2個元素 int i=(left+right)/2; /取中點(diǎn) mergeSort(a, left, i); mergeS

22、ort(a, i+1, right); merge(a, b, left, i, right); /合并到數(shù)組b copy(a, b, left, right); /復(fù)制回數(shù)組a 第31頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.5 合并排序算法mergeSort的遞歸過程可以消去。重點(diǎn)講Merge的過程,參考教材P36。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97第32頁,共38頁,2022年,5月20日,19點(diǎn)36分,星期三2.5 復(fù)雜度分析:W(n) = W(n/2)+W(n/

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論