【正文】 V)： 取變量 V之地址所消耗的時間 T(=) ： 賦值所消耗時間 T(θ) ： 執(zhí)行基本運(yùn)算 θ所耗時間 T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時間 T(par) ： 將參數(shù) par傳給函數(shù)所消耗時間 ～ . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 10 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 漸近空間復(fù)雜度（空間復(fù)雜度） S（ n） S（ n） = O（ g（ n）） 運(yùn)算法則 ： 設(shè)： T1(n)=O( f(n) )， T2(n)=O( g(n) ) 加法規(guī)則： T1(n)+T2(n) = O( max{ f(n), g(n) } ) 乘法規(guī)則： T1(n) 秋 遞歸技術(shù) —— 最常用的算法設(shè)計思想，體現(xiàn)于許多優(yōu)秀算法之中 分治法 —— 分而制之的算法思想，體現(xiàn)了一分為二的哲學(xué)思想 模擬法 —— 用計算機(jī)模擬實際場景，經(jīng)常用于與概率有關(guān)的問題 貪心算法 —— 采用貪心策略的算法設(shè)計 狀態(tài)空間搜索法 —— 被稱為“萬能算法”的算法設(shè)計策略 隨機(jī)算法 —— 利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向 動態(tài)規(guī)劃 —— 常用的最優(yōu)化問題解決方法 “好”的算法的標(biāo)準(zhǔn) ： ①正確性，算法能滿足具體問題的需求 ②可讀性，首先方便閱讀與交流，其次才是機(jī)器執(zhí)行 ③健壯性，輸入錯誤時，能作出反應(yīng)，避免異常出錯 ④效率與低存儲量要求 算法的特征 ： ① 有窮性、 ② 確定性、 ③ 輸入、 ④ 輸出、 ⑤ 能行性 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 5 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 s algorithm)聯(lián)系在一起。由 algorism又變成 algorithm。rizm 寫了著名的書 Kitab al jabr w39。rizm 的本地人”。rizm （約公元前 825年） —— 從字面上看，這個名字的意思是“ Ja39。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了 algorism(算術(shù) )一詞的真實起源：它來源于著名的 Persian Textbook(《 波斯教科書 》 )的作者的名字 Abu Ja39。 秋 資料： Algorithm與 Logarithm 這個詞一直到 1957年之前在 Webster39。rizm 是前蘇聯(lián) XИBA(基發(fā) ) 的小城鎮(zhèn) 。s226。s226。在這個過程中，無論是形成解題思路還是編寫程序 ,都是在實施某種算法。 秋 第二章 算法設(shè)計與分析的基本方法及技巧 程序運(yùn)行時間 一類遞歸方程的求解 分治 平衡 貪心法 動態(tài)規(guī)則 回溯 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 2 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 算法（ Algorithm） ：是對特定問題求解步驟的一種描述，它是 指令（規(guī)則）的有限序列，其中每一條指令表示一個或多個操作。前者是推理實現(xiàn)的算法，后者是操作實現(xiàn)的算法。 alKhow226。 的兒子， Khow226。 AlKhow226。s New World Dictionary(《 韋氏新世界詞典 》 )中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“ Algorism”( 算術(shù) )，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過程。far Mohammed ibn Mfar 的父親，Mohammed 和 M Khow226。almuqabala (《 復(fù)原和化簡的規(guī)則 》 )；另一個詞，“ algebra”( 代數(shù) )，是從他的書的標(biāo)題引出來的，盡管這本書實際上根本不是講代數(shù)的。一本早期的德文數(shù)學(xué)詞典 Vollstandiges Mathematisches Lexicon (《 數(shù)學(xué)大全辭典 》 ) ，給出了 Algorithmus (算法 )一詞的如下定義：“在這個名稱之下，組合了四種類型的算術(shù)計算的概念，即加法、乘法、減法、除法”。這個算法就是在歐幾里德的 《 幾何原本 》 (Euclid39。 秋 對算法“正確性”的要求 ： ① 不含語法錯誤； ② 對于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果； ③ 對精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果； ④ 對于一切合法的輸入均得到滿足要求的結(jié)果； 算法描述 ： ① 自然語言； ② 程序設(shè)計語言； ③ 類語言 *； 關(guān)于本書采用的類語言描述 ： ① 結(jié)構(gòu)類型說明 ② 輸入輸出約定 ( cin v , cout v ) ③ new 和 delete ④ 引入引用類型 ⑤ 其他 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 6 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 T2(n) = O( f(n) 秋 (1) 表達(dá)式和賦值語句 exp::=常數(shù) | 變量 | Fname(e1,e2,…,e m) | (exp θ exp) T(v=exp)=T(.v)+T(=)+T(exp) T(exp θ exp)=T(exp)+T(θ)+T(exp) T(Fname(e1,e2,…,e m))=T(call/return)+mT(par)+T(Fbody) 例： T(c=a+b)=T(.c)+T(=)+T(a)+T(+)+T(b) 相應(yīng)的匯編程序為： load a in R1 load b in R2 add R2 to R1 load .c in R2 store R1 in R2 ～ ～ 通常取 O(1) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 11 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 秋 (5) for語句 T( for(i=1。 i++} 設(shè) RT0表示某一次循環(huán)開始執(zhí)行時的絕對時間 關(guān)于循環(huán)的定時不變式 RT為 RT=RT0+(i+1)(T(B)+T(while)+i(T(s)+T(j)) 其中： T(while)代表測試循環(huán)終止條件所耗時間 T(j)代表跳回循環(huán)頭所耗時間 可簡化成： T(j)=T(while) T(while(B)s)=RTRT0=(i+1)T(B)+iT(s)+(2i+1)T(while) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 13 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 for(i=0。j) O(∑(ni1)) if(A[j1]A[j]) { O((ni1) 1) ≤O(n(n1)/2) temp=A[j1]。 秋 舉例 ： ① s = 0 。 ++i ) { ++x。 i=n 。 s += x。 ++i ) for ( j=1 。 k = n。 秋 舉例 ： ⑤ Long fact ( int n) { if ( n==0 ) || ( n ==1 ) return( 1 )。 { if(i==j) return(x[i])。 秋 猜解法： 首先猜出一個解 f(n)的形式，令其帶有待定參數(shù)；在歸納 推理過程中確定待定參數(shù)，并利用方程證明 T(n) ≤f(n)。 此猜測失敗。 使 T(n) ≤anlogn+b成立的兩個約束是： b≥c1， a≥c2+b 取 b=c1 , a=c1+c2 是合理的。全部數(shù)據(jù)被分割成 c等分，每分的 數(shù)量為 n/c。 用 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ù)結(jié)構(gòu) Slides. 2 21 第二章 算法設(shè)計與分析的基本方法與技巧 國家示范性軟件學(xué)院 2020 則有： d(ck1)=(d(c))k1 ∑ajd(ck1)=∑aj(d(c))k1