algorithm-chapter--展示頁
2025-08-02 09:08本頁面
【正文】 往往難以驗證，雖然它可能很合理。 —— 平均效率不是最優(yōu)和最差效率的平均值。以后討論平均效率時都引用已知的 推導(dǎo)結(jié)果。 所以，如果沒有平均效率分析，我們會錯失不少重要算法。 平均效率 3 平均時間效率 Cavg (n) —— 隨機輸入情況下的時間效率。 【 例 】 順序查找 Cbest (n) = 1 最優(yōu)時間效率分析的價值 遠不如最差時間效率分析重要，因不能指望每次輸入都是最優(yōu)輸入。 實際中考慮該最差效率是否可以接受。 最優(yōu)、最差效率 1 最差時間效率 Cworse (n) —— 最壞輸入（使基本操作數(shù) C(n) 最大）情況下的時間效率。 平均時間效率 上例表明：某些算法的時間效率與輸入有關(guān)。 最優(yōu)時間效率 —— 若鍵位于表尾或不存在，比較 n 次。 【 分析 】 —— 時間效率與查找鍵在表中的位置有關(guān)。 例子：順序搜索 ?算法見書 ?輸入 : 數(shù)組 A[1..n],待找元素 k ?基本操作：比較 ?其中 pi為在 A[1..n]的第 i位置找到 k的概率 ,Ci為相應(yīng)的比較次數(shù) ?Pn+1相當(dāng)于沒有找到的概率 ? ?? ?? ? ? ?w or stbe st111nav g i iiC n nCnC n E C p C?????? ?算法效率算例 ?時間效率的類別 【 考慮 】 算法的時間效率與特定輸入有關(guān)嗎？ 【 算法 】 順序查找 【 要求 】 在線性表中查找一次 給定項（鍵） ，該表有 n 個元素。 ?平均效率 是指在“典型”或“隨機”輸入的情況下，算法具有的行為（效率）。 階乘 指數(shù) 三次 二次 nlogn 線性 對數(shù) 規(guī)模 1018 1012 107 106 20 106 1015 1010 106 105 17 105 1012 108 105 104 13 104 109 106 104 103 10 103 10157 1030 106 104 102 102 102 106 210 103 102 101 101 101 n! 2n n3 n2 nlog2n n1 log2n n 指 數(shù) 增 長 * 一個指數(shù)級操作次數(shù)的算法只能用來解決規(guī)模非常小的問題 分析框架 —— 算法的最優(yōu)、最差和平均效率 ?算法的最優(yōu)、最差和平均效率 ?最差效率是指在輸入規(guī)模為 n時，算法在最壞情況下的效率。因為 t 減少 10 倍， C(n) 不變。 ?基本操作通常是算法最內(nèi)層循環(huán)中最費時的操作。它們對算法 執(zhí)行時間的占用最大。 問： 統(tǒng)計算法 每步操作執(zhí)行次數(shù) 作為算法的時間度量，如何？ 答： 無此必要，且分析復(fù)雜困難（若干變量）?？紤]輸入規(guī)模的選擇？ 輸入規(guī)模：數(shù)值的 二進制位數(shù)。 輸入規(guī)模的選擇，也可能受算法本身的影響。 【 例 】 輸入規(guī)模選擇 【 算法 】 計算兩個 n 階矩陣的乘積，可選擇兩種不同的輸入規(guī)模 1. 矩陣的階 n 2. 參與乘法運算的元素總數(shù) 方法 1 簡單直接，適合于方陣。 ?經(jīng)常使用一個輸入規(guī)模 n為參數(shù)的函數(shù)來研究算法的效率。 Time is Important 不是所有能計算的都有價值，不是所有有價值的都能被計算 ——阿爾伯特 .愛因斯坦 算法分析 ?需解決的問題 ?度量一個算法的時間效率 (時間費用 ) ?度量一個算法的空間效率 (空間費用 ) ?優(yōu)化算法 ?最小化一個算法的時間效率或空間效率 ?途徑 ?理論分析 ?經(jīng)驗分析 分析框架 —— 輸入規(guī)模度量 ?輸入規(guī)模度量 ?算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量。算法分析與設(shè)計 Analysis and Design of Computer Algorithms 第二章 算法效率分析基礎(chǔ) 軟件設(shè)計實踐（ ACM程序設(shè)計） 教學(xué)內(nèi)容 ?算法效率分析框架 ?算法效率的表示符號 ?非遞歸算法的效率分析 ?遞歸算法的效率分析 ?算法的經(jīng)驗分析 ?要求 ?掌握算法中近似時間的表示、非遞歸、遞歸算法的效率分析方法，了解算法的經(jīng)驗分析 3 為什么要進行算法效率分析？ ?新問題 設(shè)計出復(fù)雜性盡可能低的算法 ?當(dāng)給定的問題已有多種算法時，選擇其中復(fù)雜性最低者 。 應(yīng)怎樣進行算法效率分析？ 4 算法效率分析基礎(chǔ) ?算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。 ?對于所有的算法，對于規(guī)模更大的輸入都需要運行更長的時間。 ?選擇輸入規(guī)模的合適量度，要受到所討論算法的操作細節(jié)影響。方法 2 具一般性，適于非方陣。如下例： 【 算法 】 文字拼寫檢查 算法要求 —— 檢查每個字符 輸入規(guī)模：字符數(shù) 算法要求 —— 檢查每個單詞 輸入規(guī)模：單詞數(shù) 若算法與數(shù)值本身大小有關(guān)，如大整數(shù)相乘。 比十進制位數(shù)更準(zhǔn)確 ?耗費時間的度量 為何不選擇時間的標(biāo)準(zhǔn)度量（秒、毫秒等）度量算法的運行時間呢？ —— 它依賴于特定計算機系統(tǒng)的運行速度 —— 它依賴于實現(xiàn)算法的代碼質(zhì)量（程序員的編程水平）
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1