【正文】 所以，本例選乘法為基本操作。 算法 MaxElement(A[0..n1] //求給定數(shù)組中的最大元素 //輸入：實數(shù)數(shù)組 A[0..n1] //輸出： A中的最大元素 maxval ?A[0] for i ? 1 to n1 do if A[i] maxval maxval ? A[i] return maxval 考慮： 1. 循環(huán)中的操作有比較和賦值，取哪一個作為基本操作？ 2. 輸入規(guī)模是多少？ 基本操作為： 比較運算 輸入規(guī)模就是數(shù)組長度 n 算法的效率為： 分析非遞歸算法效率的通用方案 1. 決定用那些參數(shù)作為輸入規(guī)模的度量。 順序查找算法的平均時間效率 【 例 】 順序查找算法的平均時間效率分析 假設： —— 查找成功的概率 = p ，不成功的概率 = 1 p —— 查找鍵位于任一位置上的概率都相等 = 1 / n * 任一位置上查找成功的概率 = p 1 / n * k 位置查找成功： 比較次數(shù) = k p 1 / n = p k / n * k 位置查找不成功：比較次數(shù) = n (1p) ??? ? ? ? ????? ? ? ? ? ? ? ? ? ??? ? ????????? ? ? ?????( 1 )(112...10()( 1 )( 1 2 .. . ) ( 1 ) ( 1 )2( 1 )() / 2 ,1)2a v gCnp p n nnnknp p p pn n n nnpnnppp n pnnpnnp攤銷效率 4 攤銷效率 算法單次運行的時間代價較昂貴， n 次運行的 總耗時則明顯低于單次 運行耗時乘以 n ，單次運行的成本分攤到各次運行中 —— 攤銷效率 它與商業(yè)中把固定資產(chǎn)成本按年限攤銷到各年中的做法一致。 時間效率類別：最佳、最差、平均時間效率。 【 結論 】 算法時間效率度量 —— 基本操作的執(zhí)行次數(shù) 分析框架 —— 運行時間的度量單位 分析框架 —— 運行時間的度量單位 ?運行時間的度量單位 ?用算法的基本操作（算法中最重要的操作）的 執(zhí)行次數(shù) 來度量算法的時間效率。算法分析與設計 Analysis and Design of Computer Algorithms 第二章 算法效率分析基礎 軟件設計實踐（ ACM程序設計） 教學內容 ?算法效率分析框架 ?算法效率的表示符號 ?非遞歸算法的效率分析 ?遞歸算法的效率分析 ?算法的經(jīng)驗分析 ?要求 ?掌握算法中近似時間的表示、非遞歸、遞歸算法的效率分析方法，了解算法的經(jīng)驗分析 3 為什么要進行算法效率分析？ ?新問題 設計出復雜性盡可能低的算法 ?當給定的問題已有多種算法時，選擇其中復雜性最低者 。 ?基本操作通常是算法最內層循環(huán)中最費時的操作。 最優(yōu)、最差效率 1 最差時間效率 Cworse (n) —— 最壞輸入（使基本操作數(shù) C(n) 最大）情況下的時間效率。通常， 具備這種特性的算法，具有一定程度上的 智能 ，通過學習累積知識， 對下次運行提供指導，提高下次運行的時間效率。 2. 找出算法的基本操作。 效率類別： 本例基本操作數(shù)只與輸入規(guī)模有關，與輸入元素分布無關， 不用分析最佳、最差和平均效率?？紤]操作的時間耗費：大多數(shù)計算機的乘法比加法更 費時，算術運算比賦值操作更費時。 非遞歸算法的數(shù)學分析 ?Example 1：討論下面這個算法（從 n個元素中查找最大元素問題）的效率。 但是，輸入的 概率模型 往往難以驗證，雖然它可能很合理。 平均時間效率 上例表明：某些算法的時間效率與輸入有關。它們對算法 執(zhí)行時間的占用最大。 應怎樣進行算法效率分析？ 4 算法效率分析基礎 ?算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。 ?算法運行時間的估計： T(n) ≈ copC(n) ?n是該算法的輸入規(guī)模 ?cop是特定計算機上一個算法基本操作的執(zhí)行時間 ?C(n)是該算法需要執(zhí)行的基本操作的次數(shù) 問： 為什么是約等于？ 忽略了非基本操作執(zhí)行時間 分析框架的應用例 【 時間效率分析例 】 1 機器速度提高 10 倍，算法運行時間降低多少？ 答： 10 倍。 最差時間效率分析的價值 對任意輸入規(guī)模， 保證算法運行時間不超過最壞輸入時的運行時間。 【 例 】 動態(tài)詞頻調整算法（漢字鍵盤輸入法） 統(tǒng)計用戶對某些字詞的使用頻率（學習過程），動態(tài)調整這些字詞 下次出現(xiàn)的順序（高頻先現(xiàn)），減少用戶查找次數(shù)，提高算法效率。 3. 檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。 建立增長函數(shù) C(n) ： 1 1 1 1 1 10 0 0 0 0 0112 3120030( ) 111()n n n n n ni j i j i jnnkniinCnnnnnn? ? ? ? ? ?? ? ? ? ??? ???????? ?