11-編程的靈魂——數(shù)據(jù)結構+算法=程序(文件)
【正文】 例 2： 2n3 = O(7n8) ? 類似的，可以定義下限 Ω ? 如果上下限相等，增長情況完全一樣 ,記做 Θ ? 由于上限有無限多個，我們希望它盡量精確 , 否則我們的分析就過于悲觀了，實際算法沒那么糟糕 五、遞歸式的遞歸樹分析 遞歸式 ? 在很多時候 , 無法寫出時間復雜度 T(n)的顯式表達式 , 而只能得到遞歸方程 – 公式一 : T(1)=1, T(n)=T(n1)+n, 則 T(n)為 n(n+1)/2 – 公式二 : T(1)=1, T(n)=T(n/2)+1, 則 T(n)約為 lgN – 公式三 : T(1)=0, T(n)=T(n/2)+n, 則 T(n)約為 2n – 公式四 : T(1)=0, T(n)=2T(n/2)+n, 則 T(n)約為 nlgN – 公式五 : T(1)=1, T(n)=2T(n/2)+1, 則 T(n)約為 2n ? 考慮一般情形 : T(n) = aT(n/b) + f(n) 遞歸樹分析 ? T(n) = aT(n/b) + f(n), a, b為常數(shù)， f(n)為給定函數(shù) ? 遞歸樹 : T(n) = f(n)+af(n/b)+a2f(n/b2)+…+ aLf(n/bL) ? 其中最后一項為遞歸邊界，即 n/bL=1，因此 L=logbn 公式四分析 ? 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 – a = 2, b = 2, f(n) = n –對于第 k項，有 2kf(n/2k) = 2k *n/2k = n –一共有 log2n項 – T(n) = n * log2n = O(nlogn) 小結 ? 基本概念 –時空開銷，增長，漸進復雜度 –基本操作， 輸入規(guī)模、偽多項式算法、多項式算法（有效算法） ? 常用符號 – O（上限）、 Ω（下限）、 Θ（相同）； – o（松的） ? 時間復雜度和運行時間的關系 小結 ? 分析對象 –不同輸入的運行時間：最壞、最好、平均 –一定概率假設下的運行時間：期望 –不同效率的多個操作：平攤 ? 時空辨證關系 –時間換空間：重復計算 –空間換時間：預處理 六、算法設計與分析實例 最大連續(xù)序列問題 ? 給一串整數(shù) a[1… n]，求出它和最大的子序列，即找出 1=i=j=n，使a[i]+a[i+1]+…+ a[j]最大 ? 介紹四個算法并分析時間復雜度 –枚舉： O(n3) –優(yōu)化的枚舉： O(n2) –分治： O(nlogn) –貪心： O(n) 算法一 max := a[1]。 end。 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。例：停機問題 ? 廣義 ChurchTuring命題：如果一個函數(shù)在某個合理的計算模型上使用合理時間復雜性度量是多項式時間可計算的，那么它在圖靈機上也是多項式時間可計算的 ? 挑戰(zhàn)：量子 TM上找到了整數(shù)因子分解問題的多項式時間解 其他概念 ? 計數(shù)復雜性： P完全問題 ? 概率： RP（只允許單邊失誤）和 ZPP（期望多項式時間） .定理： ZPP = RP∩coRP ? 近似算法 –多項式時間近似方案 (PTAS)：近似比 r = 1 + 1/k，存在算法 Ak， k常數(shù)時為多項式算法 –完滿多項式時間近似方案 (FPTAS)： Ak的運算時間同時也是 k的多項式函數(shù) . 例：背包問題中，設 M為最大價值，做價值替換 ui=[vin(k+1)/M]，近似比 1+1/(k1) 小結 ? RAM模型 ? 非確定機、 NP完全問題、 3SAT的 NP完全性、多項式時間多對一歸約 ? 計數(shù)復雜性，概率復雜性和近似復雜性 八、總結 一、緒論 ? 問題、實例、算法 ? 輸入、輸出與算法步驟（偽代碼 /代碼） ? 算法與數(shù)據(jù)結構的關系 ? 算法改進與硬件投資的比較；核心算法在項目中的作用 二、算法的實現(xiàn)與比較 ? 算法的重用性 ? 基本算法的實現(xiàn)：微調、新計算環(huán)境 ? 簡潔性、教育性與效率的權衡 ? 真實實現(xiàn)：過度優(yōu)化、錯誤處理、維護性的考慮 ? 算法分析和實驗比較的側重點 ? 實驗比較時的代碼編寫 ? 測試數(shù)據(jù)的設計 ? 待定參數(shù)的調節(jié) 三、算法分析 ? 三個任務（比較、預測、設置參數(shù)）、挑戰(zhàn)、基礎（理想模型） ? 時間分析的對象：起決定因素部分的基本操作數(shù)量的合理近似 ? 輸入建模：隨機數(shù)據(jù)、針對性數(shù)據(jù) 四、函數(shù)增長和記號 ? 主要參數(shù) n，操作數(shù)函數(shù) f(n) ? 增長的含義、最高項 ? 常見的函數(shù)增長和運行時間 ? 常見函數(shù)的近似 ? 復雜度常用記號，上限和下限 五、遞歸式的遞歸樹分析 ? 遞歸方程 T(n) = aT(n/b) + f(n) ? 遞歸樹得到的結果： – T(n) = f(n)+af(n/b)+a2f(n/b2)+…+
畢業(yè)設計相關推薦
鄂ICP備17016276號-1