1、第一節(jié)計算20:41第一章緒論第一節(jié) 1.1.1 計算計算是本課程直接研究對象和內容，也是研究的目的和最終目標；計算的本質的內在規(guī)律，一般方型技巧。進行有效的，高效的計算，同時低廉的資源消耗。1.1.2 繩索計算機計算機：12條等長的繩索；計算：用繩索求解過直線外一點垂線的方法。屏幕剪輯的捕獲時間: 2016/7/15 21:001.1.3 尺規(guī)計算機計算機：尺規(guī)；計算：做三等分點的作圖過程；屏幕剪輯的捕獲時間: 2016/7/15 21:071.1.4 算法算法：特定計算模型下，旨在解決特定問題的指令序列。特點要素：輸入輸出 正確性確定性可行性有窮性1.1.5 有窮性待處理信息（問題）經處理

2、信息（ ）可解決指定問題語義明確操作可實現(xiàn)，且在常數(shù)時間內完成基本操作次數(shù)程序！=算法 （死循環(huán)，棧溢出）分區(qū) 數(shù)據(jù)結構 的第 1 頁1.1.6 好算法效率：速度盡可能快；空間盡可能少；正確，健壯（處理輸入），可讀分區(qū) 數(shù)據(jù)結構 的第 2 頁第二節(jié)計算模型22:131.2.1 性能測度1.2.2 問題規(guī)模算法分析：主要有兩個方面：正確性：算能與問題要求是否一致成本：運行時間+ 所需空間復雜度與問題規(guī)模有關，歸納可采用：劃分等價類。一般問題實例的規(guī)模，往往是決定計算成本的主要 上升）。（規(guī)模擴大，計算成本1.2.3情況定義T（n）為規(guī)模為n的實例的復雜度。（然而，同一問題等規(guī)模的不同實例計算成本

3、不盡相同），所以有以下定義：T（n）= max （T（P）| |P| = n）；即選取出等規(guī)模中的情況。1.2.4 理想模型排除不同算法對輸入規(guī)模、類型的適應性，不同程序語言，不同編譯器、體系結構，操作系統(tǒng)等具體法。的影響，從而抽象出一個理想的或模型，來評價算1.2.5 圖靈機無限長的紙帶（T），讀寫頭（Head），有限種狀態(tài)（Se），有限的字母表（Alphabet）1.2.6 圖靈機的實例（讀寫頭當前狀態(tài)，當前字符，改變后字符，左右移，改變后讀寫頭狀態(tài)，）屏幕剪輯的捕獲時間: 2016/7/17 20:321.2.7 RAM Random Acs Machine 模型（隨機器）分區(qū) 數(shù)據(jù)結構

4、 的第 1 頁屏幕剪輯的捕獲時間: 2016/7/17 20:441.2.8 RAM 實例4屏幕剪輯的捕獲時間: 2016/7/17 20:53若能夠整除，是否需要-1？（需要，c+1）分區(qū) 數(shù)據(jù)結構 的第 2 頁第三節(jié)大記號21:021.3.1 主流長遠評價DSA時，不要拘泥于暫時變化。觀察主要的、長遠的變化趨勢1.3.2屏幕剪輯的捕獲時間: 2016/7/17 21:26屏幕剪輯的捕獲時間: 2016/7/17 21:261.3.3 高效解常數(shù)復雜度對數(shù)多項式（對數(shù)）復雜度屏幕剪輯的捕獲時間: 2016/7/17 21:361.3.4 有效解多項式復雜度分區(qū) 數(shù)據(jù)結構 的第 1 頁1.3.

5、5 難解指數(shù)復雜度（通常被認為是無效算法）指數(shù)復雜度的算法通常容易看出，但要加以改進為多項式復雜度，通常很。1.3.6 例子 2-subset 子集plete（）1.3.7 增長速度屏幕剪輯的捕獲時間: 2016/7/17 22:03分區(qū) 數(shù)據(jù)結構 的第 2 頁第一節(jié)算法分析19:442.1.1 算法分析C+等高級語言的基本指令，均等效于常數(shù)條RAM基本指令；在漸進意義下，二者大體相當。分支轉向：goto/算法；出于結構化考慮，被隱蔽了迭代循環(huán)：for()、while()/本質為“if + goto”調用+ 遞歸/本質也是goto復雜度分析主要方法迭代：級數(shù)求和遞歸：遞歸猜測 + 驗證+ 遞歸

6、方程2.1.2 級數(shù)屏幕剪輯的捕獲時間: 2016/7/21 20:03屏幕剪輯的捕獲時間: 2016/7/21 20:052.1.3 循環(huán)分區(qū) 數(shù)據(jù)結構 的第 1 頁屏幕剪輯的捕獲時間: 2016/7/21 20:10屏幕剪輯的捕獲時間: 2016/7/21 20:15屏幕剪輯的捕獲時間: 2016/7/21 20:242.1.4 非元素+ 起泡排序分區(qū) 數(shù)據(jù)結構 的第 2 頁屏幕剪輯的捕獲時間: 2016/7/21 20:50非元素：有些算法，不論規(guī)模n有多大，可能需要執(zhí)行時間是一個常數(shù)。2.1.5 起泡排序正確性說明屏幕剪輯的捕獲時間: 2016/7/21 20:572.1.6 封地估算

7、-1 Some history2.17 封地估算-2屏幕剪輯的捕獲時間: 2016/7/21 21:11分區(qū) 數(shù)據(jù)結構 的第 3 頁屏幕剪輯的捕獲時間: 2016/7/21 21:11分區(qū) 數(shù)據(jù)結構 的第 4 頁第二節(jié)迭代與遞歸18:302.2.1 迭代與遞歸2.2.2 減而治之屏幕剪輯的捕獲時間: 2016/8/7 20:572.2.3 遞歸【線性遞歸】檢查每個遞歸實例累計所需時間（調用語句本身，計入相應的子實例），其中和即算法執(zhí)行時間。屏幕剪輯的捕獲時間: 2016/8/7 21:152.2.4 遞歸方程遞歸方程：根據(jù)算法結構得出一個遞推式，進而通過求解方程得出顯式的復雜度的解。遞歸基：“

8、遞歸基”是遞歸函數(shù)的一種平凡情況，只有有遞歸基，遞歸才不會一直進行下去。2.2.5 數(shù)組倒置分區(qū) 數(shù)據(jù)結構 的第 1 頁屏幕剪輯的捕獲時間: 2016/8/7 21:342.2.6 分而治之屏幕剪輯的捕獲時間: 2016/8/7 21:352.2.7 二分遞歸：數(shù)組求和二叉樹圖，類似于二。屏幕剪輯的捕獲時間: 2016/8/7 21:482.2.8 二分遞歸：MAX2屏幕剪輯的捕獲時間: 2016/8/7 21:58迭代 2分區(qū) 數(shù)據(jù)結構 的第 2 頁屏幕剪輯的捕獲時間: 2016/8/7 22:012.2.9 MAX2：二分迭代屏幕剪輯的捕獲時間: 2016/8/7 22:14分區(qū) 數(shù)據(jù)結構

9、 的第 3 頁第三節(jié)動態(tài)規(guī)劃10:322.3.1 動態(tài)規(guī)劃屏幕剪輯的捕獲時間: 2016/8/13 10:48動態(tài)規(guī)劃可以理解為，通過遞歸，找出了算法的本質，并且給出一個初步的解之后再將其等效地轉化為迭代的形式對于數(shù)列，采用簡單的遞歸方法，解決問題所用時間非常之長，效率非常低。2. 3.2 FIB():遞推方程屏幕剪輯的捕獲時間: 2016/8/13 16:24數(shù)列的通項公式：由復雜度T(n)的運算，構造出S(n)。而S(n)恰恰是數(shù)列的第n+1項。由此計算復雜度。對于1.2.數(shù)列通項公式計算，參考線性遞歸數(shù)列的特征方程數(shù)列的通項公式求法2.3.3 FIB():封地估算分區(qū) 數(shù)據(jù)結構 的第 1

10、 頁屏幕剪輯的捕獲時間: 2016/8/14 16:232.3.4 FIB(): 遞歸應用實例一個階的過程在某一個樓梯允許你每次走一步 也可以每次走兩步 那么請問上到某一級比如說第6級臺階的時候總共有多少種走法？（這個數(shù)字就是對應的，比如 第6階的話就是第6項Fibonacci數(shù)）2.3.5 FIB():迭代屏幕剪輯的捕獲時間: 2016/8/14 16:552.3.6 LCS：最長公共子序列子序列：由序列中若干字符，按原相對次序。最長公共子序列：可能有多個，可能有歧義（重復字符）2.3.7 LCS：遞歸屏幕剪輯的捕獲時間: 2016/8/14 17:19分區(qū) 數(shù)據(jù)結構 的第 2 頁屏幕剪輯的捕獲時間: 2016/8/14 17:202.3.8 LCS：理解屏幕剪輯的捕獲時間: 2016/8/14 21:152.3.9 LCS：復雜