【正文】 load b in R2 add R2 to R1 load .c in R2 store R1 in R2 ～ ～ 通常取 O(1) . 算法與數(shù)據(jù)結構 Slides. 2 11 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 一本早期的德文數(shù)學詞典 Vollstandiges Mathematisches Lexicon (《 數(shù)學大全辭典 》 ) ，給出了 Algorithmus (算法 )一詞的如下定義：“在這個名稱之下，組合了四種類型的算術計算的概念，即加法、乘法、減法、除法”。far Mohammed ibn M alKhow226。在這個過程中，無論是形成解題思路還是編寫程序 ,都是在實施某種算法。 秋 資料： Algorithm與 Logarithm 這個詞一直到 1957年之前在 Webster39。rizm 寫了著名的書 Kitab al jabr w39。 漸近空間復雜度（空間復雜度） S（ n） S（ n） = O（ g（ n）） 運算法則 ： 設： T1(n)=O( f(n) )， T2(n)=O( g(n) ) 加法規(guī)則： T1(n)+T2(n) = O( max{ f(n), g(n) } ) 乘法規(guī)則： T1(n) { int I,j,temp。 T2(n) = O(f(n)) = O(n) 線性階 ③ for ( i=1。 T4(n) = O(f(n)) = O(n3) 立方階 . 算法與數(shù)據(jù)結構 Slides. 2 16 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 當 n≥2時，設對所有的 kn 有 T(k) ≤aklogk+b 令 k=n/2 得 T(n/2) ≤a(n/2)log(n/2)+b 帶入原式： T(n) ≤2T(n/2)+c2n≤2(a(n/2)log(n/2)+b)+c2n =an(logn1)+c2n+2b =anlogn+b(anc2nb) 只要令 anc2nb≥0就有 T(n) ≤anlogn+b 選擇 a≥c2+b，使 anc2nb≥0得到滿足。 秋 基本思想：分而治之。2n/2+b) d a b c d x= y= . 算法與數(shù)據(jù)結構 Slides. 2 26 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 104+(ad=8 秋 在對問題進行分割時，應使各子問題的數(shù)據(jù)量保持相等或盡可能 相等。 i++ ) { x = select(A)。 假設需要找給小孩 6 7美分，首先入選的是兩枚 2 5美分的硬幣，第三枚入選的不能是 2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過 6 7美分），第三枚應選擇 1 0美分的硬幣，然后是 5美分的，最后加入兩個 1美分的硬幣。 按策略 2，首先取 x3=1,次取 x2=2/3,得解 3。 } L : if ( i = n ) x[i] = cu / w[i] 。 } . 算法與數(shù)據(jù)結構 Slides. 2 38 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 因此，如果決定不取 w1，則 求解 Knap(1,n,M)的問題即歸結為求解子問題 Knap(2,n,M)。 } write(mln) 。 l++ ) for( i=1 。這與 y1,y2,…,y n是最佳序列相矛盾 ,說明最佳原理適用于 0/1背包問題。 n 1 ) return False。 i = n 。即 按 pi/wi非增加的順序來選擇對象。假設提供了數(shù)目不限的面值為 2 5美分、 1 0美分、 5美分、及 1美分的硬幣。 Dataset Gready(A, n) LIST A 。T(n/2)+n2 U(n)=4m/a102+(15+34)101+3=1632 b=41 a2=4 b2=1 a2b2=3 d=27 c2=2 d2=7 d2c2=5 a2d=(1107)*, (ab) c+ (ab) 秋 整數(shù)乘法 求兩個 n位數(shù)之積，傳統(tǒng)方法需要 O(n2)次比較運算，運用分治 法可以將運算次數(shù)的階降到 O(nlog3) ≈O()。 若 d(n)是倍積函數(shù)。 設有： T(n) ≤ c1 n=1 2T(n/2)+c2n n1 猜測 1： 對參數(shù) a， T(n) ≤anlogn，帶入 n=1，由于 anlogn=0 雖然滿足 T(1) ≤c1，但它與 a無關，無法確定 a與 c1關系。 for ( k=1 。 i = n 。while(B) { s 。 秋 遞歸技術 —— 最常用的算法設計思想，體現(xiàn)于許多優(yōu)秀算法之中 分治法 —— 分而制之的算法思想，體現(xiàn)了一分為二的哲學思想 模擬法 —— 用計算機模擬實際場景，經常用于與概率有關的問題 貪心算法 —— 采用貪心策略的算法設計 狀態(tài)空間搜索法 —— 被稱為“萬能算法”的算法設計策略 隨機算法 —— 利用隨機選擇自適應地決定優(yōu)先搜索的方向 動態(tài)規(guī)劃 —— 常用的最優(yōu)化問題解決方法 “好”的算法的標準 ： ①正確性，算法能滿足具體問題的需求 ②可讀性，首先方便閱讀與交流，其次才是機器執(zhí)行 ③健壯性，輸入錯誤時，能作出反應，避免異常出錯 ④效率與低存儲量要求 算法的特征 ： ① 有窮性、 ② 確定性、 ③ 輸入、 ④ 輸出、 ⑤ 能行性 . 算法與數(shù)據(jù)結構 Slides. 2 5 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 rizm 的本地人”。rizm 是前蘇聯(lián) XИBA(基發(fā) ) 的小城鎮(zhèn) 。 秋 第二章 算法設計與分析的基本方法及技巧 程序運行時間 一類遞歸方程的求解 分治 平衡 貪心法 動態(tài)規(guī)則 回溯 . 算法與數(shù)據(jù)結構 Slides. 2 2 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 的兒子， Khow226。far 的父親，Mohammed 和 M這個算法就是在歐幾里德的 《 幾何原本 》 (Euclid39。 秋 (5) for語句 T( for(i=1。 秋 舉例 ： ① s = 0 。 ++i ) for ( j=1 。 秋 猜解法： 首先猜出一個解 f(n)的形式，令其帶有待定參數(shù)；在歸納 推理過程中確定待定參數(shù)，并利用方程證明 T(n) ≤f(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) i1 j=0 . 算法與數(shù)據(jù)結構 Slides. 2 21 第二章 算法設計與分析的基本方法與技巧 國家示范性軟件學院 2020 為了解決一個大的問題，可以： 1) 把它分成兩個或多個更小的問題； 2) 分別解決每個小問題； 3) 把各小問題的解組合起來，即可得到原問題的解答。y=a 秋 例：設 x=3141, y=5327, 利用分治法求 xd1=3, (a1b1) T(n/2)+an2/4 n2 其中第一項是計算 m對 (n/2) (n/2)矩陣之積的時間開銷 ,(n/2)2個數(shù) 第二項是 a次矩陣相加的時間開銷。 給定輸入數(shù)據(jù)為 A[1],A[2],…,A[n] ，對解附有某些約束條件 和表示最佳結果的目標函數(shù)，欲求滿足約束條件的子集 A[ik],使 目標函數(shù)值達到最大（或最小）。作出貪婪決策的依據(jù)稱為貪婪準則（ greedy criterion）。 (2)貪心策略之二：背包容量局部消耗最小策略。 i++ ) x[i] = 0 。 秋 ???