11-編程的靈魂——數據結構算法=程序(存儲版)
【正文】 的設計 ? 待定參數的調節(jié) 三、算法分析 ? 三個任務（比較、預測、設置參數）、挑戰(zhàn)、基礎（理想模型） ? 時間分析的對象：起決定因素部分的基本操作數量的合理近似 ? 輸入建模：隨機數據、針對性數據 四、函數增長和記號 ? 主要參數 n，操作數函數 f(n) ? 增長的含義、最高項 ? 常見的函數增長和運行時間 ? 常見函數的近似 ? 復雜度常用記號，上限和下限 五、遞歸式的遞歸樹分析 ? 遞歸方程 T(n) = aT(n/b) + f(n) ? 遞歸樹得到的結果： – T(n) = f(n)+af(n/b)+a2f(n/b2)+…+ aLf(n/bL) –其中 L=logbn ? T(n) = 2T(n/2) + n，則 T(n)=O(nlogn) 六、算法設計與分析實例 ? 最大連續(xù)序列問題 – 算法一：完全枚舉 O(n3) – 算法二：利用前綴和優(yōu)化枚舉 O(n2) – 算法三：分治 O(nlogn) – 算法四：掃描 O(n) ? 思考題：最大連續(xù)子矩陣問題 – 給一個矩陣，每個元素 aij為整數 – 尋找一個子矩陣 (i,j)(k,l)，使得子矩陣內數和最小 – 提示：利用算法四設計 O(n3)算法 七、計算模型與難解問題 ? RAM模型：順序執(zhí)行指令，隨機存取，基本操作需要常數時間 . 未考慮字長、層次存儲器等問題 ? 并行計算機和非確定機 ? P類問題、 NP類問題、 NP完全問題 ? 3SAT問題的 NP完全性，多項式時間多對一歸約 ? P完全問題、 RP、 ZPP問題、 PTAS和FPTAS 結束 。 for i:=1 to n do for j:=i to n do if s[j] – s[i1] max then max := s[j] – s[i1]。 end ? 第 i次循環(huán)執(zhí)行了 i個操作 ? 總時間復雜度為 1+2+3+…+ n = n(n+1)/2 ? 如果式子再長一點，怎么辦？ 小結 ? 先寫程序，直接觀察結果 –同一算法，程序不同，運行時間不同 –寫代碼太費事，如果寫出來才發(fā)現很慢 … ? 不寫程序，直接分析算法 –不寫程序怎知運行時間？“抽象操作”數 –表達式很復雜怎么辦？漸進表示 , 大 O記號 四、函數增長和記號 操作數函數 ? 在很多情況下 , 基本操作數可以寫成 N的函數 f(N), 其中 N代表主要參數 ? 例如 , 給 N個數排序的問題 , N就是主要參數 , 它最明顯的決定了問題的復雜程度 , 也影響著算法效率 ? 存在多個主參數的情況類似定義 , 本節(jié)暫不考慮 比較兩個算法 ? 假設有兩個算法 –算法一執(zhí)行了 f(n)=n2次基本操作 –算法二執(zhí)行了 g(n)=n2/2次基本操作 ? 那個算法好呢？ –絕對操作數算法二好，因為 g(n) f(n) –增長情況呢？ ? n擴大 10倍， f(n)擴大 100倍， g(n)也擴大 100倍 ? 兩個算法的增長情況一樣！ ? 我們說 : 漸進時間復雜度 一樣！ 漸進時間復雜度 ? f(n)=n2和 g(n)=n2/2 –結論 : 增長情況一樣 –問題 : 如何表示“增長情況”？ –方法 : 把 f(n)和 g(n)變成“漸進”形式，然后直接比較 ? 如何變成“漸進”形式？ 只保留最“大”項 , 忽略系數 , 符合前面介紹的原則 –例 1： 3n4+8n2+n+2 ? n4 –例 2： 2n+1+n100+5 ? 2n (為什么 n+1變成了 n？ ) 常見的函數增長 ? f(N)的漸進形式往往是以下某個函數 – 1(常數 , constant): 和 N無關 , N多大運行時間都一樣 – logN(對數 , logarithmic): 這是個增長緩慢的函數 . 若底為 2, 則 log1000000約為 20 – N(線性 , linear): 對于必須處理 N個輸入數據 , 或者得到 N個輸出數據的問題 , 算法 (在漸進意義下 )是最優(yōu)的 . – N2(平方 , quadratic): 若 N加倍 , 函數值變?yōu)樗谋? – 2N(指數級 , exponential): N很小時 2N已經很大了 ? 多項式算法 Na: 有效算法 函數增長和運行時間 對數函數 ? 若 bL=n, 記 L = logbn，稱 L為以 b為底的n的對數 ? 對數的公式 – logan + logam = loganm – klogan = logank –換底公式： logan/logbn=logba ? 對數是一種增長很慢的函數 – log21000 約為 10 – log21000000 約為 20 對數函數 ? 由于算法分析忽略常數，通常 logN不指定底 , 默認情況為 2, 記為 lgN, 若底為自然對數e(=), 記為 lnN ? lgN為 N二進制表示中的位數 ,lg10= ? 有時也取對數的對數 loglogN. 由于lglg1012=, 所以一般可以把它看作常數 其他常見函數和近似 復雜度分析不清楚怎么辦 ? 只分析上限，而不需要精確計算實際運行時間 – 若 n充分大
畢業(yè)設計相關推薦
鄂ICP備17016276號-1