【正文】 ???????? ? ? ? ?? ? ? ? ? ???? ? ? ? ???? ? ? ????? ????? ??? ? ?????20( 1 ) ( 1 ) ( 2 ) ( 3 ) 111 2 ( 1 ) ( 1 )2nin n n nninn??? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ??【 例 】 矩陣乘法的時(shí)間效率分析 給定兩個(gè)方陣 A 和 B，根據(jù)矩陣乘法定義計(jì)算它們之乘積。 2. 找出算法的基本操作。 性質(zhì) 4 理解 某些算法由兩個(gè)以上的部分組成。通常， 具備這種特性的算法，具有一定程度上的 智能 ，通過學(xué)習(xí)累積知識(shí)， 對下次運(yùn)行提供指導(dǎo)，提高下次運(yùn)行的時(shí)間效率。 所以，如果沒有平均效率分析，我們會(huì)錯(cuò)失不少重要算法。 最優(yōu)、最差效率 1 最差時(shí)間效率 Cworse (n) —— 最壞輸入（使基本操作數(shù) C(n) 最大）情況下的時(shí)間效率。 例子：順序搜索 ?算法見書 ?輸入 : 數(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?????? ?算法效率算例 ?時(shí)間效率的類別 【 考慮 】 算法的時(shí)間效率與特定輸入有關(guān)嗎？ 【 算法 】 順序查找 【 要求 】 在線性表中查找一次 給定項(xiàng)（鍵） ，該表有 n 個(gè)元素。 ?基本操作通常是算法最內(nèi)層循環(huán)中最費(fèi)時(shí)的操作。 輸入規(guī)模的選擇，也可能受算法本身的影響。算法分析與設(shè)計(jì) Analysis and Design of Computer Algorithms 第二章 算法效率分析基礎(chǔ) 軟件設(shè)計(jì)實(shí)踐（ ACM程序設(shè)計(jì)） 教學(xué)內(nèi)容 ?算法效率分析框架 ?算法效率的表示符號(hào) ?非遞歸算法的效率分析 ?遞歸算法的效率分析 ?算法的經(jīng)驗(yàn)分析 ?要求 ?掌握算法中近似時(shí)間的表示、非遞歸、遞歸算法的效率分析方法，了解算法的經(jīng)驗(yàn)分析 3 為什么要進(jìn)行算法效率分析？ ?新問題 設(shè)計(jì)出復(fù)雜性盡可能低的算法 ?當(dāng)給定的問題已有多種算法時(shí)，選擇其中復(fù)雜性最低者 。方法 2 具一般性，適于非方陣。 【 結(jié)論 】 算法時(shí)間效率度量 —— 基本操作的執(zhí)行次數(shù) 分析框架 —— 運(yùn)行時(shí)間的度量單位 分析框架 —— 運(yùn)行時(shí)間的度量單位 ?運(yùn)行時(shí)間的度量單位 ?用算法的基本操作（算法中最重要的操作）的 執(zhí)行次數(shù) 來度量算法的時(shí)間效率。 ?攤銷效率是指對于同樣的數(shù)據(jù)結(jié)構(gòu)執(zhí)行多次操作，然后分?jǐn)偟矫恳淮紊稀? 時(shí)間效率類別：最佳、最差、平均時(shí)間效率。 平均時(shí)間效率分析的價(jià)值 有許多重要算法的平均效率比它們過于悲觀的最差效率要好很多。 順序查找算法的平均時(shí)間效率 【 例 】 順序查找算法的平均時(shí)間效率分析 假設(shè)： —— 查找成功的概率 = 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 攤銷效率 算法單次運(yùn)行的時(shí)間代價(jià)較昂貴， n 次運(yùn)行的 總耗時(shí)則明顯低于單次 運(yùn)行耗時(shí)乘以 n ，單次運(yùn)行的成本分?jǐn)偟礁鞔芜\(yùn)行中 —— 攤銷效率 它與商業(yè)中把固定資產(chǎn)成本按年限攤銷到各年中的做法一致。 ?該定理表明： 當(dāng)算法由兩個(gè)連續(xù)執(zhí)行部分組成時(shí)，該算法的整體效率由具有較大增長次數(shù)的那部分所決定。 算法 MaxElement(A[0..n1] //求給定數(shù)組中的最大元素 //輸入：實(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)中的操作有比較和賦值，取哪一個(gè)作為基本操作？ 2. 輸入規(guī)模是多少？ 基本操作為： 比較運(yùn)算 輸入規(guī)模就是數(shù)組長度 n 算法的效率為： 分析非遞歸算法效率的通用方案 1. 決定用那些參數(shù)作為輸入規(guī)模的度量。這時(shí)，完成全部循環(huán) 比較次數(shù) = 循環(huán)次數(shù) 。所以，本例選乘法為基本操作。