【正文】 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 1 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 第二章 算法設(shè)計(jì)與分析的基本方法及技巧 程序運(yùn)行時(shí)間 一類遞歸方程的求解 分治 平衡 貪心法 動(dòng)態(tài)規(guī)則 回溯 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 2 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 算法（ Algorithm） ：是對(duì)特定問(wèn)題求解步驟的一種描述，它是 指令（規(guī)則）的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則。通俗點(diǎn)說(shuō) ,就是計(jì)算機(jī)解題的過(guò)程。在這個(gè)過(guò)程中，無(wú)論是形成解題思路還是編寫(xiě)程序 ,都是在實(shí)施某種算法。前者是推理實(shí)現(xiàn)的算法，后者是操作實(shí)現(xiàn)的算法。 Persian Textbook(《 波斯教科書(shū) 》 )的作者的名字 Abu Ja39。far Mohammed ibn Ms226。 alKhow226。rizm （約公元前 825年） —— 從字面上看，這個(gè)名字的意思是“ Ja39。far 的父親， Mohammed 和 Ms226。 的兒子， Khow226。rizm 的本地人”。 Khow226。rizm 是前蘇聯(lián) XИBA(基發(fā) ) 的小城鎮(zhèn) 。 AlKhow226。rizm 寫(xiě)了著名的書(shū) Kitab al jabr w39。almuqabala (《 復(fù)原和化簡(jiǎn)的規(guī)則 》 )； . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 3 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 資料： Algorithm與 Logarithm 這個(gè)詞一直到 1957年之前在 Webster39。s New World Dictionary(《 韋氏新世界詞典 》 )中還未出現(xiàn)，我們只能找到帶有它的古代涵義的較老形式的“ Algorism”( 算術(shù) )，指的是用阿拉伯?dāng)?shù)字進(jìn)行算術(shù)運(yùn)算的過(guò)程。在中世紀(jì)時(shí)，珠算家用算盤(pán)進(jìn)行計(jì)算，而算術(shù)家用算術(shù)進(jìn)行計(jì)算。中世紀(jì)之后，對(duì)這個(gè)詞的起源已經(jīng)拿不準(zhǔn)了，早期的語(yǔ)言學(xué)家試圖推斷它的來(lái)歷，認(rèn)為它是從把 algiros(費(fèi)力的 )+arithmos(數(shù)字 )組合起來(lái)派生而成的，但另一些人則不同意這種說(shuō)法，認(rèn)為這個(gè)詞是從“喀斯迪爾國(guó)王 Algor” 派生而來(lái)的。最后，數(shù)學(xué)史學(xué)家發(fā)現(xiàn)了 algorism(算術(shù) )一詞的真實(shí)起源：它來(lái)源于著名的 Persian Textbook(《 波斯教科書(shū) 》 )的作者的名字 Abu Ja39。far Mohammed ibn Ms226。 alKhow226。rizm （約公元前 825年） —— 從字面上看，這個(gè)名字的意思是“ Ja39。far 的父親，Mohammed 和 Ms226。 的兒子， Khow226。rizm 的本地人”。 Khow226。rizm 是前蘇聯(lián) XИ BA(基發(fā) ) 的小城鎮(zhèn) 。 AlKhow226。rizm 寫(xiě)了著名的書(shū) Kitab al jabr w39。almuqabala (《 復(fù)原和化簡(jiǎn)的規(guī)則 》 )；另一個(gè)詞，“ algebra”( 代數(shù) )，是從他的書(shū)的標(biāo)題引出來(lái)的，盡管這本書(shū)實(shí)際上根本不是講代數(shù)的。 逐漸地，“ algorism” 的形式和意義就變得面目全非了。如牛津英語(yǔ)字典所說(shuō)明的，這個(gè)詞是由于同 arithmetic(算術(shù) )相混淆而形成的錯(cuò)拼詞。由 algorism又變成 algorithm。一本早期的德文數(shù)學(xué)詞典 Vollstandiges Mathematisches Lexicon (《 數(shù)學(xué)大全辭典 》 ) ，給出了 Algorithmus (算法 )一詞的如下定義：“在這個(gè)名稱之下，組合了四種類型的算術(shù)計(jì)算的概念，即加法、乘法、減法、除法”。拉頂短語(yǔ) algorithmus infinitesimalis (無(wú)限小方法 ) ，在當(dāng)時(shí)就用來(lái)表示Leibnitz(萊布尼茲 )所發(fā)明的以無(wú)限小量進(jìn)行計(jì)算的微積分方法。 1950年左右， algorithm一詞經(jīng)常地同歐幾里德算法 (Euclid39。s algorithm)聯(lián)系在一起。這個(gè)算法就是在歐幾里德的 《 幾何原本 》 (Euclid39。s Elements ,第 VII卷，命題 i和 ii)中所闡述的求兩個(gè)數(shù)的最大公約數(shù)的過(guò)程 (即輾轉(zhuǎn)相除法 )。 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 4 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 遞歸技術(shù) —— 最常用的算法設(shè)計(jì)思想，體現(xiàn)于許多優(yōu)秀算法之中 分治法 —— 分而制之的算法思想，體現(xiàn)了一分為二的哲學(xué)思想 模擬法 —— 用計(jì)算機(jī)模擬實(shí)際場(chǎng)景，經(jīng)常用于與概率有關(guān)的問(wèn)題 貪心算法 —— 采用貪心策略的算法設(shè)計(jì) 狀態(tài)空間搜索法 —— 被稱為“萬(wàn)能算法”的算法設(shè)計(jì)策略 隨機(jī)算法 —— 利用隨機(jī)選擇自適應(yīng)地決定優(yōu)先搜索的方向 動(dòng)態(tài)規(guī)劃 —— 常用的最優(yōu)化問(wèn)題解決方法 “好”的算法的標(biāo)準(zhǔn) ： ①正確性，算法能滿足具體問(wèn)題的需求 ②可讀性，首先方便閱讀與交流，其次才是機(jī)器執(zhí)行 ③健壯性，輸入錯(cuò)誤時(shí)，能作出反應(yīng)，避免異常出錯(cuò) ④效率與低存儲(chǔ)量要求 算法的特征 ： ① 有窮性、 ② 確定性、 ③ 輸入、 ④ 輸出、 ⑤ 能行性 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 5 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 對(duì)算法“正確性”的要求 ： ① 不含語(yǔ)法錯(cuò)誤； ② 對(duì)于幾組輸入數(shù)據(jù)能得到滿足要求的結(jié)果； ③ 對(duì)精心選擇苛刻并帶有刁難的數(shù)據(jù)能得到滿足要求的結(jié)果； ④ 對(duì)于一切合法的輸入均得到滿足要求的結(jié)果； 算法描述 ： ① 自然語(yǔ)言； ② 程序設(shè)計(jì)語(yǔ)言； ③ 類語(yǔ)言 *； 關(guān)于本書(shū)采用的類語(yǔ)言描述 ： ① 結(jié)構(gòu)類型說(shuō)明 ② 輸入輸出約定 ( cin v , cout v ) ③ new 和 delete ④ 引入引用類型 ⑤ 其他 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 6 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 影響算法執(zhí)行的因素 ： ①算法實(shí)現(xiàn)后所消耗的時(shí)間 ** ②算法實(shí)現(xiàn)后所占存儲(chǔ)空間的大小 * ③算法是否易讀、易移植等等其它問(wèn)題 影響時(shí)間特性的四個(gè)因素 ： ①程序運(yùn)行時(shí)輸入數(shù)據(jù)的總量 ②對(duì)源程序編譯所需的時(shí)間 ③計(jì)算機(jī)執(zhí)行每條指令所需的時(shí)間 ④程序中指令重復(fù)執(zhí)行的次數(shù) * [定義 ] 語(yǔ)句頻度 ：語(yǔ)句重復(fù)執(zhí)行的次數(shù) ?程序運(yùn)行時(shí)間 . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 7 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 漸近時(shí)間復(fù)雜度（時(shí)間復(fù)雜度） T（ n） 算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模 n的某個(gè)函數(shù) f（ n），算法的時(shí)間度量記作： T（ n） = O（ f（ n）） 它表示隨問(wèn)題規(guī)模 n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和 f（ n）的增長(zhǎng)率相同。 漸近空間復(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) T2(n) = O( f(n) g(n) ) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 8 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 程序運(yùn)行時(shí)間比較 T（ n） =O（ f（ n）） T(n) n 0 1000 2020 3000 5 10 15 20 25 2n n3 100n 5n2 logn 2100 △ n △ T(n) . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 9 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 設(shè)： T(x) ： 取變量或常量 x之值所消耗時(shí)間 T(.V)： 取變量 V之地址所消耗的時(shí)間 T(=) ： 賦值所消耗時(shí)間 T(θ) ： 執(zhí)行基本運(yùn)算 θ所耗時(shí)間 T(call/return)：執(zhí)行函數(shù)調(diào)用和返回所耗時(shí)間 T(par) ： 將參數(shù) par傳給函數(shù)所消耗時(shí)間 ～ . 算法與數(shù)據(jù)結(jié)構(gòu) Slides. 2 10 第二章 算法設(shè)計(jì)與分析的基本方法與技巧 國(guó)家示范性軟件學(xué)院 2020 秋 (1) 表達(dá)式和賦值語(yǔ)句 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)的匯編程序?yàn)椋?