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