第二章 算法設計與分析的基本方法及技巧,2.1 程序運行時間 2.2 一類遞歸方程的求解 2.3 分治 2.4 平衡 2.5 貪心法 2.6 動態規則 2.7 回溯,算法（Algorithm）：是對特定問題求解步驟的一種描述，它是 指令（規則）的有限序列，其中每一條指令表示一個或多個操作。,算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說,就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序,都是在實施某種算法。前者是推理實現的算法，后者是操作實現的算法。,Persian Textbook(波斯教科書)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （約公元前825年） 從字面上看，這個名字的意思是“Jafar 的父親，Mohammed 和 Ms 的兒子，Khowrizm 的本地人”。Khowrizm 是前蘇聯XBA(基發) 的小城鎮 。Al-Khowrizm 寫了著名的書Kitab al jabr wal-muqabala (復原和化簡的規則)；,資料：Algorithm與Logarithm 這個詞一直到1957年之前在Websters New World Dictionary(韋氏新世界詞典)中還未出現，我們只能找到帶有它的古代涵義的較老形式的“Algorism”(算術)，指的是用阿拉伯數字進行算術運算的過程。在中世紀時，珠算家用算盤進行計算，而算術家用算術進行計算。中世紀之后，對這個詞的起源已經拿不準了，早期的語言學家試圖推斷它的來歷，認為它是從把algiros(費力的)+arithmos(數字)組合起來派生而成的，但另一些人則不同意這種說法，認為這個詞是從“喀斯迪爾國王Algor”派生而來的。最后，數學史學家發現了algorism(算術)一詞的真實起源：它來源于著名的Persian Textbook(波斯教科書)的作者的名字Abu Jafar Mohammed ibn Ms al-Khowrizm （約公元前825年）從字面上看，這個名字的意思是“Jafar 的父親，Mohammed 和 Ms 的兒子，Khowrizm 的本地人”。Khowrizm 是前蘇聯XBA(基發) 的小城鎮 。Al-Khowrizm 寫了著名的書Kitab al jabr wal-muqabala (復原和化簡的規則)；另一個詞，“algebra”(代數)，是從他的書的標題引出來的，盡管這本書實際上根本不是講代數的。 逐漸地，“algorism”的形式和意義就變得面目全非了。如牛津英語字典所說明的，這個詞是由于同arithmetic(算術)相混淆而形成的錯拼詞。由algorism又變成algorithm。一本早期的德文數學詞典 Vollstandiges Mathematisches Lexicon (數學大全辭典) ，給出了Algorithmus (算法)一詞的如下定義：“在這個名稱之下，組合了四種類型的算術計算的概念，即加法、乘法、減法、除法”。拉頂短語algorithmus infinitesimalis (無限小方法) ，在當時就用來表示Leibnitz(萊布尼茲)所發明的以無限小量進行計算的微積分方法。 1950年左右，algorithm一詞經常地同歐幾里德算法(Euclids algorithm)聯系在一起。這個算法就是在歐幾里德的幾何原本(Euclids Elements ,第VII卷，命題i和ii)中所闡述的求兩個數的最大公約數的過程(即輾轉相除法)。,遞歸技術 最常用的算法設計思想，體現于許多優秀算法之中 分治法 分而制之的算法思想，體現了一分為二的哲學思想 模擬法 用計算機模擬實際場景，經常用于與概率有關的問題 貪心算法 采用貪心策略的算法設計 狀態空間搜索法 被稱為“萬能算法”的算法設計策略 隨機算法 利用隨機選擇自適應地決定優先搜索的方向 動態規劃 常用的最優化問題解決方法,“好”的算法的標準： 正確性，算法能滿足具體問題的需求 可讀性，首先方便閱讀與交流，其次才是機器執行 健壯性，輸入錯誤時，能作出反應，避免異常出錯 效率與低存儲量要求,算法的特征： 有窮性、確定性、輸入、輸出、能行性,對算法“正確性”的要求： 不含語法錯誤； 對于幾組輸入數據能得到滿足要求的結果； 對精心選擇苛刻并帶有刁難的數據能得到滿足要求的結果； 對于一切合法的輸入均得到滿足要求的結果；,算法描述： 自然語言；程序設計語言；類語言*；,關于本書采用的類語言描述： 結構類型說明 輸入輸出約定( cin v , cout v ) new 和 delete 引入引用類型 其他,影響算法執行的因素： 算法實現后所消耗的時間* 算法實現后所占存儲空間的大小* 算法是否易讀、易移植等等其它問題,影響時間特性的四個因素： 程序運行時輸入數據的總量 對源程序編譯所需的時間 計算機執行每條指令所需的時間 程序中指令重復執行的次數*,定義 語句頻度：語句重復執行的次數,程序運行時間,漸近時間復雜度（時間復雜度）T（n）,算法中基本操作重復執行的次數是問題規模n的某個函數 f（n），算法的時間度量記作： T（n）= O（ f（n） 它表示隨問題規模n的增大，算法執行時間的增長率和 f（n）的增長率相同。,漸近空間復雜度（空間復雜度）S（n）,S（n）= O（ g（n）,運算法則： 設：T1(n)=O( f(n) )，T2(n)=O( g(n) ) 加法規則：T1(n)+T2(n) = O( max f(n), g(n) ) 乘法規則：T1(n) T2(n) = O( f(n) g(n) ),設：,T(x) ： 取變量或常量x之值所消耗時間 T(.V)： 取變量V之地址所消耗的時間 T(=) ： 賦值所消耗時間 T() ： 執行基本運算所耗時間 T(call/return)：執行函數調用和返回所耗時間 T(par) ： 將參數par傳給函數所消耗時間,(1) 表達式和賦值語句 exp:=常數 | 變量 | F-name(e1,e2,em) | (exp exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp exp)=T(exp)+T()+T(exp) T(F-name(e1,e2,em)=T(call/return)+mT(par)+T(F-body) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相應的匯編程序為： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2,通常取O(1),(2) 語句序列 T(s1,s2,sk)=maxT(s1),T(s2),T(sk) (3) 條件語句 T( if (B) s1 else s2)=T(B)+T(else)+maxT(s1),T(s2) 通常取T(B)+T(else)=O(1) T(if(B) s )=O(1)+T(s) (4) Switch語句 設語句s switch(E) case E1: S1; case Ek: Sk; default : Sm T(s)=T(E)+T(Ei)+maxT(s1),T(sk),T(sm) O(1),k i=1,(5) for語句 T( for(i=1;i=n;i+) s ) =(T(s)+T(i=1)+T(i=n)+T(i+)+T(for),O(1),(6) while語句 while(B) s i=0;while(B) s ; i+ 設RT0表示某一次循環開始執行時的絕對時間 關于循環的定時不變式RT為 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j) 其中：T(while)代表測試循環終止條件所耗時間 T(j)代表跳回循環頭所耗時間 可簡化成：T(j)=T(while) T(while(B)s)=RT-RT0=(i+1)T(B)+iT(s)+(2i+1)T(while),(7) 函數調用 遞歸調用：被調用子函數運行時間 非遞歸調用：求解遞歸方程 (8) goto語句 goto語句破壞了程序結構 一般對goto語句限制使用 對有條件的goto轉移可忽略不計,Void BUBBLE(A) int An; int I,j,temp; for(i=0;i=i+1;j-) O(n-i-1) if(Aj-1Aj) O(n-i-1) 1) O(n(n-1)/2) temp=Aj-1; O(1) O(1) =(n-i-1) =O(n2) Aj-1=Aj; O(1) O(1) Aj=temp; O(1) ,n-2 i=0,舉例： s = 0 ; f(n) = 1; T1(n) = O(f(n) = O(1) 常量階 for ( i=1 ; i = n ; +i ) +x; s += x; f(n) = 3n+1; T2(n) = O(f(n) = O(n) 線性階 for ( i=1; i=n ; +i ) for( j=1 ; j =n ; +j ) +x ; s += x; f(n) = 3n2+2n+1; T3(n) = O(f(n) = O(n2) 平方階 for ( i=1; i=n ; +i ) for ( j=1 ; j =n ; +j ) cij = 0; for ( k=1 ; k = n; +k ) cij += aik * bkj ; f(n) = 2n3+3n2+2n+1; T4(n) = O(f(n) = O(n3) 立方階,舉例： Long fact ( int n) if ( n=0 ) | ( n =1 ) return( 1 ); else return( n * fact( n 1 ) ); ,f( n ) = n G T( n ) = O( f( n ) ) = O( n ),int sort(i,j) int i,j; if(i=j) return(xi); else m=(i+j-1)/2; return(merge(sort(i,m),sort(m+1),j); ,這是一個快速排序算法 merge的運行時間正比于n（n是2的冪） 設T(n)是sort最差情況下的運行時間，則,一類遞歸方程的求解,猜解法： 首先猜出一個解f(n)的形式，令其帶有待定參數；在歸納 推理過程中確定待定參數，并利用方程證明T(n) f(n)。 若推理過程能夠完成且待定參數能夠確定，則求解完畢。 f(n)可以是 O(1) , O(n) , O(nlogn) , O(n2)等等。,猜測1：對參數a，T(n) anlogn，帶入n=1，由于anlogn=0 雖然滿足T(1) c1，但它與a無關，無法確定a與c1關系。 此猜測失敗。,猜測2：T(n)=anlogn+b，當n=1時，只要bc1即可。 當n2時，設對所有的 kn 有 T(k) aklogk+b 令k=n/2 得 T(n/2) a(n/2)log(n/2)+b 帶入原式： T(n) 2T(n/2)+c2n2(a(n/2)log(n/2)+b)+c2n =an(logn-1)+c2n+2b =anlogn+b-(an-c2n-b) 只要令an-c2n-b0就有 T(n) anlogn+b 選擇ac2+b，使an-c2n-b0得到滿足。 使T(n) anlogn+b成立的兩個約束是： bc1，ac2+b 取b=c1 , a=c1+c2 是合理的。,一類遞歸方程的展開式與通解,設T(n)是求解某個問題的時間開銷，n使問題的數據量。設計 對此問題列出的遞歸方程為： T(1)=1 T(n)=aT(n/c)+d(n) n2 其中c是大于等于1的正整數。全部數據被分割成c等分，每分的 數量為n/c。T(n/c)是求解一個子問題的時間開銷。aT(n/c)代表求 解a個問題的時間開銷。D(n)是任意的函數，方程是嚴格的等式。 用n/ci代替n得： T(n/ci)=aT(n/ci+1)+d(n/ci), i=1,2,3, T(n)=aT(n/c)+d(n) =a(aT(n/c2)+d(n/c)+d(n)=a2T(n/c2)+ad(n/c)+dn =a2(aT(n/c3)+d(n/c2)+ad(n/c)+d(n) =a3T(n/c3)+a2d(n/c2)+ad(n/c)+d(n) = =ai T(n/ci)+ajd(n/cj),i-1 j=0,倍積函數：若對所有的正整數x，y，有f(xy)=f(x)f(y)，則 f 是 正整數上的倍積函數。 若d(n)是倍積函數。則有： d(ck-1)=(d(c)k-1,定理：設a,c是非負常數，n是2的冪，d(n)是倍積函數，則,的齊次解是O(nlogc )，且對特解有如下結論： (1)若ad(c)，則特解是O(ak)，或O(nlogc ),即特解與齊次解同階 (2)若ad(c)，則特解是O(d(c)k)，或O(nlogcd(c)即特解與d同階 (3)若a=d(c)，則特解是齊次解的logcn。,a,a,基本思想：分而治之。將一個規模為n的問題分解為k個規模較小 的子問題，這些子問題互相獨立且與原問題相同。遞 歸地解這些子問題，然后將各子問題的解合并得到原 問題的解。,設問題輸入數據A0n-1，函數dac(p,q)求子問題Ap,q的解。 對函數dac的首次調用是dac(0,n-1)。,int dac(int p, int q) if(small(p,q) return(G(p,q); else (m1,mk)=divide(p,q); return(Combine(dac(p,m1),dac(m1+1,m2), ,dac(mk+1,q); ,分治方法與軟件設計的模塊化方法非常相似。為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別解決每個小問題； 3) 把各小問題的解組合起來，即可得到原問題的解答。 小問題通常與原問題相似，可以遞歸使用分治策略來解決。,分治（Divide and Conquer ）,1、整數乘法,求兩個n位數之積，傳統方法需要O(n2)次比較運算，運用分治 法可以將運算次數的階降到O(nlog3) O(n1.59)。,設x和y都是n位數，n是2的冪，將x和y各分成兩半，每一半都 是n/2位數，則xy的積可寫成：,xy=(a2n/2+b) (c2n/2+d) =ac2n+(ad+bc) 2n/2+bd 也可寫成： xy=ac2n+ac+ (a-b) (d-c) +bd) 2n/2+bd,a,b,c,d,x=,y=,int mult(int x, int y,int n) if(n=1) return(x*y); else s=sign(x)*sign(y); x=abs(x); y=abs(y); a=x的左n/2位； b=x的右n/2位； c=y的左n/2位； d=y的右n/2位； v=mult(a,c,n/2); u=mult(a-b,d-c,n/2); w=mult(b,d,n/2); return(s*(v*2n+(u+v+w)*2n/2+w) ,例：設 x=3141, y=5327, 利用分治法求xy,31,41,53,27,x=,y=,x=3141 a=31 b=41 a-b=-10 y=5327 c=53 d=27 d-c=-26 ac=(1643)*, bd=(1107)*, (a-b) (d-c)=(260)* xy=ac104+(ac+(a-b) (d-c)+bd) 102+bd =(1643)*104+(1643)*+(260)*+(1107)* 102+(1107)* =(16732107)*,a=31 a1=3 b1=1 a1-b1=2 c=53 c1=5 d1=3 d1-c1=-2 a1c1=15, b1d1=3, (a1-b1) (d1-c1)=-4 ac=15102+(15+3-4)101+3=1632,b=41 a2=4 b2=1 a2-b2=3 d=27 c2=2 d2=7 d2-c2=5 a2c2=8, b2d2=7, (a2-b2) (d2-c2)=15 bd=8102+(8+7+15)101+7=1107,a-b=10 a3=1 b3=0 a3-b3=1 d-c=26 c3=2 d3=6 d3-c3=4 a3c3=2, b3d3=0, (a3-b3) (d3-c3)=4 (a-b) (d-c)=2102+(2+0+4) 101+0=260,2、求兩個矩陣的積,C11=A11B11+A12B21 C12=A11B12+A12B22 C21=A21B11+A22B21 C22=A21B12+A22B22,將A和B分別等分成4個小矩陣,每個元素就是一個(n/2) x(n/2)矩陣,假設用(n/2) (n/2)矩陣的m次相乘和a次相加（減）可以算出Cij， 則遞歸應用這種算法，對nn矩陣之積的時間開銷滿足： T(n)2 其中第一項是計算m對(n/2) (n/2)矩陣之積的時間開銷,(n/2)2個數 第二項是a次矩陣相加的時間開銷。上是可變換成： 4/aT(n)=4m/aT(n/2)+n2 U(n)=4m/aU(n/2)+n2 其中d(n)=n2是倍積函數，只要ma就有4m/ad(c)，T(n)=O(nlogm) m=8,a=4，T(n)=O(n3),V.Strassen矩陣,引理2.1 兩個22矩陣(元素來自任意的環)之積可以用7次相乘和 18次相加(減)完成。,M1=(A11A12)(B21+B22) M2=(A11+A22)(B11+B22) M3=(A11A21)(b11+B12) M4=(A11+A12)B22 M5=A11(B12-B22) M6=A22(B21B11) M7=(A21+A22)B11,C11=M1+M2-M4+M6 C12=M4+M5 C21=M6+M7 C22=M2M3+M5M7,定理2.2 兩個nn的矩陣(元素來自任意的環)之積可用O(nlog7)次 運算完成 證：設n=2k，T(n)是計算兩個nn矩陣之積，由引理2.1得 T(n)=7T(n/2)+18(n/2)2，n=2 故有：T(n)=O(nlog7),在對問題進行分割時，應使各子問題的數據量保持相等或盡可能 相等。保持平衡是算法設計的一條基本原則。,例如：常見的是“冒泡”分類算法就是一個不平衡的例子。 在分治時將輸入數據a1,a2,an分成很不平衡的數據段： 從左至右掃描a1,a2,an并求出minai,1=i=n；將它與 a1交換位置；對后面的n-1個元素遞歸地應用此算法。,T(n)=n(n-1)/2=O(n2),考慮平衡：不妨設n是2的冪。將a1,a2,an分成兩個子序列： a1,a2,an/2和a(n/2)+1,an。先對每個子序列進行分類，然后 對已分類的子序列進行歸并（最多需要n-1次比較），合并成一 個有序序列。,T(n)=O(nlogn),平衡,運用局部最佳策略以求達到全局最佳結果。 給定輸入數據為A1,A2,An，對解附有某些約束條件 和表示最佳結果的目標函數，欲求滿足約束條件的子集Aik,使 目標函數值達到最大（或最小）。 滿足約束條件的任意子集叫做可用解，使給定的目標值達到 最大（或最小）的可用解叫做最佳解。最終目的是求全局最佳解。,Dataset Gready(A, n) LIST A ; int n ; solution = ； for( i = 1; i = n; i+ ) x = select(A); if ( feasible( solution, x ) ) solution = union ( solution , x ) ; return solution ; ,select 對 A 確定一種取值辦法；每步對 一個x=Ai作出判斷：x是否可以包含在 最佳解中？若x加入局部最佳解時就產生 不可用解，放棄x，另作選擇。,union將x和solution結合成新的解向量,并 修改目標函數的值。,貪心法,在貪心算法（greedy method）中采用逐步構造最優解的方法。在每個階段，都作出一個看上去最優的決策（在一定的標準下）。決策一旦作出，就不可再更改。作出貪婪決策的依據稱為貪婪準則（greedy criterion）。,例找零錢 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。 假設需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數超過6 7美分），第三枚應選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。,背包問題 設有n個對象和一個背包。對象的重量為wi。背包容量為M(重量)。 若將對象i的一部分xi(0xi1;xi表示重物wi的幾分之幾)放入背包， 則得增益pixi，其中pi叫做重物wi的增益率。目標:在n個對象中選 取若干對象，將背包裝滿(所選對象的總重量不超過M),使總增 益最大。,max(pixi) ,1in,約束條件：wixiM 0xi1, pi0, wi0, 1in 滿足的任意集合x1,x2,xn就是可用解 使最大的可用解即最佳解,1in,三種貪心策略： (1)局部最大增一策略：即在第i步選過之后第i+1步將當前增益 最大的未選對象裝入背包；若該對象太大而溢出背包，則裝 入該對象的幾分之幾。 (2)貪心策略之二：背包容量局部消耗最小策略。即按先輕后重 的順序來選擇對象。 (3)貪心策略之三：消耗單位容量，獲取局部最大增益策略。即 按pi/wi非增加的順序來選擇對象。,例：設n=3,M=20,(p1,p2,p3)=(25,24,15),(w1,w2,w3)=(18,15,10),按策略1，對象1的增益率p1最大，取x1=1, 則背包容量尚余M-w1=2;對象2的增益率次 之,但w2=15,不能全部裝入,故令x2=2/15,得解2。 按策略2，首先取x3=1,次取x2=2/3,得解3。 按策略3，得解4，這才是最佳解。,Void KnapSack (LIST w ; int m ; LIST ,Pi/wi=(1.4,1.6,1.5),定理2.3 若 p1/w1p2/w2pn/wn 則算法Knapsack對給定的 背包問題生成全局最佳解。 證明見教材P42（略）。,實例： 設有一個背包可以放入的物品的重量為s，現有n件物品，重量分 別為w1, w2, , wn。問能否從這n件物品中選擇若干件放入 此背包中，使得放入的重量之和正好為S。 如果存在一種符合上 述要求的選擇，則稱此背包問題有解(或稱其解為真)；否則稱此 背包問題無解(或稱其解為假)。試用遞歸方法設計求解背包問題 的算法。,enum boolean False, True boolean Kanp( int s, int n ) if ( s = 0 ) return True; if ( s 0 ,當一個問題的解可以看成是以序列判定的結果時，可以用動態 規劃方法設計出這類問題的求解算法。,起源于二十世紀五十年代（貝爾曼B.E.Bellman） 屬于現代控制理論的一部分 以長遠利益為目標的一系列決策 最優化原理，可歸結為一個遞推公式 又稱為對階段規劃，特點體現在多階段性,動態規劃,背包問題的解可以看成是一序列判定的結果，這里必須決定xi(1in)的取值。我們可以用不盡的方式首先做關于x1的判定,然后關于x2,x3,等等.最后產生一個最佳的判定序列x1,x2,xn,使目標函數pixi的值最大。,最佳原理 一個最佳判定序列有這樣一個性質：無論該序列是從什么初始 狀態開始首次判斷的，其后續的判斷隊首次判斷所產生的狀態 而言，必構成最佳判定序列。 貪心法與動態規劃方法之間的本質區別： 貪心法只生成一個判定序列，而動態規劃方法則可能產生許多 判定序列。,maxpixi,1ij,例：（0/1）背包問題用Knap(1,I,y)表示下述0/1背包問題,約束條件：wixiy， xi=0 或 1 （ 1ij）,1ij,則0/1背包問題是knap(1,n,M),wiziM-w1 ，pizipixi,2in,2in,2in,設：y1,y2,yn是x1,x2,xn所取0/1值的最佳序列。,若y1=0, y2,y3,yn必構成關于Knap(2,n,M)的最佳序列。不然，y1,y2,yn就不是Knap(1,n,M)的最佳序列。,若y1=1,則y2,y3,yn必是關于knap(2,n,M-w1)的最佳序列,如不然，就會有另一個0/1序列