算法設(shè)計(jì)與分析課件：遞歸

算法設(shè)計(jì)與分析遞歸

主要內(nèi)容基本概念遞歸的例子復(fù)雜度的遞歸求解1基本概念數(shù)學(xué)中的階乘可以用遞歸表示，也可以很好的解釋遞歸邊界條件遞歸方程邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(jié)果1基本概念數(shù)學(xué)中的階乘可以用遞歸表示，也可以很好的解釋遞歸1基本概念執(zhí)行函數(shù)Factorial(3)時(shí)，會(huì)進(jìn)入函數(shù)Factorial(2)，之后進(jìn)入Factorial(1)，因Factorial(1)滿足邊界條件，返回結(jié)果1到函數(shù)Factorial(2)，F(xiàn)actorial(2)完整計(jì)算，并返回結(jié)果2到Factorial(3)，F(xiàn)actorial(3)得出結(jié)果6。進(jìn)入遞歸函數(shù)時(shí)，調(diào)用函數(shù)依舊保留其狀態(tài)。也就是說如果執(zhí)行Factorial(n)，當(dāng)遞歸調(diào)用到Factorial(1)時(shí)，系統(tǒng)中總共創(chuàng)建了100個(gè)Factorial函數(shù)1例子：斐波那契數(shù)列數(shù)列:0、1、1、2、3、5、8、13、21、34、......這個(gè)數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和1例子：漢諾塔問題1例子：漢諾塔問題1.1遞歸和迭代所有的遞歸實(shí)現(xiàn)都可以轉(zhuǎn)換為迭代實(shí)現(xiàn)嗎?反之，所有的迭代實(shí)現(xiàn)都可以通過遞歸實(shí)現(xiàn)嗎？迭代轉(zhuǎn)化為遞歸通常較簡單：二分搜索輸入：非降序排列的數(shù)組A[1…n]和元素x輸出：如果x=A[j],1

j

n,則輸出j,否則輸出0.1.low←1;high←n;j←02.while(low

high)and(j=0)3.mid←

(low+high)/2

4.ifx=A[mid]thenj←mid5.elseifx<A[mid]thenhigh←mid-16.elselow←mid+17.endwhile8.returnjbinarySearch(a,x,right,

left){while(left<=right){

middle=(left+right)/2;

if(x==a[middle])returnmiddle;

if(x>a[middle])return

binarySearch(a,

x,

right,

middle+1);

elsereturn

binarySearch(a,

x,

middle+1,

left);}

return-1;//未找到x}1.1遞歸和迭代迭代轉(zhuǎn)化為遞歸通常較簡單：選擇排序1.1遞歸和迭代迭代轉(zhuǎn)化為遞歸通常較簡單：插入排序1.1遞歸和迭代遞歸轉(zhuǎn)化為迭代時(shí)，要復(fù)雜很多如很難將漢諾塔問題轉(zhuǎn)化為循環(huán)迭代（需要通過棧）從實(shí)際上說，所有的迭代可以轉(zhuǎn)換為遞歸，但遞歸不一定可以轉(zhuǎn)換為迭代2.1生成排列遞歸實(shí)際上就是找n規(guī)模問題和<n規(guī)模問題(通常是n?1規(guī)模問題)的一個(gè)關(guān)系2.1生成排列如已知X={1,2,3}的全排列P(X)，Y={1,2,3,4}的全排列P(Y)和P(X)之間存在什么關(guān)系2.1生成排列2.1生成排列2.1生成排列算法的復(fù)雜度由if和else兩部分決定，直覺上覺得是else起決定作用輸出語句共執(zhí)行了nn！次，其中n！代表排序的總數(shù)，而每個(gè)排序有n個(gè)輸出所以復(fù)雜度由if決定為2.2整數(shù)劃分2.2整數(shù)劃分下面的方法是否可行？存在重復(fù)計(jì)算2.2整數(shù)劃分2.2整數(shù)劃分2.2整數(shù)劃分3時(shí)間復(fù)雜度計(jì)算迭代次數(shù)頻度分析使用遞歸方程3.1計(jì)算迭代次數(shù)

計(jì)算迭代次數(shù)通常，程序的運(yùn)行時(shí)間和程序的迭代次數(shù)成比例。因此計(jì)算程序的迭代次數(shù)就可以作為算法運(yùn)行時(shí)間的指示器。這在很多算法中都可以得到應(yīng)用，如查找、排序等等3.1計(jì)算迭代次數(shù)

輸入：n(n=2k

，k為某一正整數(shù))輸出：count（迭代次數(shù)）1.count←02.whilen≥13.forj←1ton4.count←count+1//執(zhí)行一次耗費(fèi)時(shí)間設(shè)為a5.endfor6.n←n/2//執(zhí)行一次耗費(fèi)時(shí)間設(shè)為d7.endwhile8.returncount分析：while迭代的次數(shù)是k+1次(因?yàn)閚≥1可以寫成n≥20,運(yùn)行過程n=2k→20)，k=logn。在每次while循環(huán)里面for依次執(zhí)行n，n/2,n/4,…,1次，所以，算法的時(shí)間復(fù)雜度為：3.1計(jì)算迭代次數(shù)

為什么在上面計(jì)算算法的時(shí)間復(fù)雜度時(shí)不考慮step6,而只是考慮step4呢？如果同時(shí)考慮step4和step6，我們有小結(jié)：使用計(jì)算迭代次數(shù)的技術(shù)來分析算法的時(shí)間復(fù)雜度時(shí)，只需要考慮最深層次的迭代。3.2頻度分析

頻度分析對于有些算法，計(jì)算迭代次數(shù)非常麻煩，有時(shí)甚至是不可能的。這時(shí)候，可以使用頻度分析。在MEGE算法中，賦值運(yùn)算具有最大頻度將A的每個(gè)元素移到B又將B的每個(gè)元素移到A所以算法復(fù)雜度為2n3.2最壞情況和平均情況分析平均情況分析：通?？紤]均勻分布情況下的復(fù)雜度如插入排序中，將第i個(gè)元素插入到前面已經(jīng)排序好的數(shù)組中插入到第1個(gè)位置，比較i-1次插入到其他位置（位置j），比較i-j+1次平均比較次數(shù)為：3.2最壞情況和平均情況分析插入排序總的平均比較次數(shù)為：插入排序最差的比較次數(shù)為：3.3復(fù)雜度的遞歸求解3.3復(fù)雜度的遞歸求解3.3.1展開法3.3.1展開法3.3.2代入法步驟先猜測解的形式再通過數(shù)學(xué)歸納法證明適用于對遞歸形式比較熟悉的情況代入法另外一用法是對展開法或者遞歸樹法求得的復(fù)雜度，進(jìn)行進(jìn)一步的確認(rèn)3.3.2代入法這個(gè)復(fù)雜度的遞歸式和快速排序的復(fù)雜度遞歸式類似，猜測其也為O(nlogn)3.3.2代入法邊界條件：3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.2代入法3.3.3遞歸樹方法3.3.3遞歸樹方法首先將T(n)看出一個(gè)節(jié)點(diǎn)，如圖展開將每個(gè)子節(jié)點(diǎn)按照T(n)方式展開從圖中可知，遞歸樹總共有l(wèi)ogn層，對每層所有節(jié)點(diǎn)的復(fù)雜度進(jìn)行累加，得出每層的復(fù)雜度為cn，葉子層的復(fù)雜度為nT(1)=nc′。所以總的復(fù)雜度T(n)=nlogn3.3.3遞歸樹方法首先將復(fù)雜度的遞歸式展開為樹的形式之后，計(jì)算樹每層的復(fù)雜度最后，將所有層的復(fù)雜度相加，得到T(n)的復(fù)雜度3.3.3遞歸樹方法這棵樹并不是滿二叉樹，最短路徑為n/2，最長路徑為n。3.3.3遞歸樹方法3.3.3遞歸樹方法3.3.4主方法主要應(yīng)用于先從簡單的形式3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法3.3.4主方法