計算復雜性和算法分析計算機科學導論第六講-資料下載頁
2025-07-21 11:25本頁面
【正文】 g(N)) ) – 但解釋 O(f(N)) + O(g(N)) 和 O(f(N)) ? O(g(N))中的+和 ?（尤其是 ?）仍然有困難 – 導致各書仍繼續(xù)使用 f(N) = O(g(N))記號，使得讀者難理解 35 復雜性的漸近行為及其階 ? 其他漸近意義下的記號 – 下界記號 ? 若 f 和 g是正整數(shù)集上的正函數(shù)，若 存在大于 0的常 數(shù) C和自然數(shù) N0，使得 N ? N0時有 f(N) ? Cg(N), 則 稱： 在 N充分大時， Cg(N)是函數(shù) f(N)的一個 下 界，記為 f(N) =? (g(N))， 并簡稱 f(N)不 小 于 g(N)的階 – 記號 ? f(N) =?(g(N)) ? f(N) = O(g(N)) ? f(N) =?(g(N)) 此時稱 f(N)和 g(N)同階 – 還有其他記號 36 復雜性的漸近行為及其階 ? 算法與漸近時間復雜性的關(guān)系 算法 漸近復雜 在 C1上可 在 C2上可 N1和 N2的關(guān)系 性 T(N) 解規(guī)模 N1 解規(guī)模 N2 ? 方程 Ti(N2i)=10Ti(N1i)是求解 N2i和 N1i之間的關(guān)系 ? 等式 Ti(N2i)=10Ti(N1i)的含義是：第 i個算法在 C1上運行 10倍于 C2上運行的時間 ， 則等號兩邊效果一樣 同一問題六個算法 , 在 C1和 C2上運行 , C2的速度是 C1 10倍 . 從 Ti(N2i)=10Ti(N1i)(i =1, … , 6)解出關(guān)系式 37 復雜性的漸近行為及其階 ? 算法與漸近時間復雜性的關(guān)系 算法 漸近復雜 在 C1上可 在 C2上可 N1和 N2的關(guān)系 性 T(N) 解規(guī)模 N1 解規(guī)模 N2 A1 N N11 N21 N21 = 10N11 A2 NlogN N12 N22 N22 ? 10N12 A3 N2 N13 N23 N23 = 10N13 A4 N3 N14 N24 N24 = 10N14 A5 2N N15 N25 N25 = N15+ log10 A6 N! N16 N26 N26=N16+小的常數(shù) 同一問題六個算法 , 在 C1和 C2上運行 , C2的速度是 C1 10倍 . 從 Ti(N2i)=10Ti(N1i)(i =1, … , 6)解出關(guān)系式見上表 3 38 復雜性的漸近行為及其階 ? 復雜性漸近分析的重要性 – 對于低效算法 ， 計算機速度數(shù) 10甚至 100倍的增長基本上不帶來求解規(guī)模的增益 – 限制求解問題規(guī)模的主要根源是算法漸近復雜性的階 ? 前四個算法的漸近時間復雜性與規(guī)模 N的一個確定的冪同階 ， 機器速度的乘法增長帶來求解規(guī)模的乘法增長 。 這類算法稱為多項式算法 ? 后兩個算法的漸近時間復雜性與規(guī)模 N的一個指數(shù)函數(shù)同階 ， 只能帶來求解規(guī)模的加法增長 – 這些結(jié)論在問題規(guī)模充分大時才成立 39 算法復雜性漸近階的分析 ? 如何分析具體算法的復雜性漸近階 – 算法是用程序來表達的 ， 算法復雜性漸近階分析就是對其程序的相應分析 – 針對所用編程語言 ， 給出一套可操作的分析規(guī)則 – 分析程序的語句 、 程序塊和函數(shù)時 ， 可用局部的規(guī)模參數(shù)作為復雜性函數(shù)的自變量 。 整個程序的復雜性函數(shù)還是以整個程序的輸入規(guī)模為自變量 – 對串行算法 ， 其時間復雜性等于相應程序每個語句的時間復雜性之和 。 若對每種語句所需時間都有度量規(guī)則 ， 則算法所需時間就是一個求和問題 – 運用 O、 ?和 ? 的運算規(guī)則就可進行所需分析 40 算法復雜性漸近階的分析 ? 基本運算和基本語句 – 賦值 、 比較運算 、 算術(shù)運算 、 邏輯運算和讀寫變量等需 1個單位時間 – 下標變量和結(jié)構(gòu)體的域的訪問等需 1個單位時間 – if(C) S1 else S2只需 TC + max(TS1, TS1)個單位時間 – while(C) S所需單位時間數(shù)： (TC + TS) ? 循環(huán)次數(shù) – 函數(shù)調(diào)用：控制轉(zhuǎn)移的時間 +執(zhí)行被調(diào)函數(shù)的時間 – 遞歸函數(shù)：需要從所需時間的歸納定義 （ 遞歸方程 ） 中求解 基于這些規(guī)則可以計算整個程序的復雜性函數(shù) 41 小 結(jié) ? 本講座小結(jié) – 概要介紹計算復雜性理論 、 計算所需資源的多少是衡量計算復雜性的依據(jù) – 概要介紹 復雜性的漸近 行為、 漸近意義下的記號O及其 運算規(guī)則、 復雜性漸近分析的重要性、算法的復雜性漸近階的分析 ? 參考書， 2022 – 帕帕李米特里烏，計算復雜性，清華大學出版社 – 王曉東，計算機算法設(shè)計與分析 , 電子工業(yè)出版社 本講座的內(nèi)容大部分取自該書 42 小 結(jié) ? 與算法分析相關(guān)課程 – 數(shù)據(jù)結(jié)構(gòu)、算法基礎(chǔ)、并行計算 ? 研究方向 – 挑戰(zhàn)性的問題之一：證明諸如 “ NP =？ P” 這類問題的解是模型相關(guān)的 – 各種新型計算模型下的核心算法 43
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1