【正文】 在最壞情況下的效率。諸多算法的效率不僅與規(guī)模 有關，且與特定的輸入有關。 T(n) 隨著 n 次數(shù)的增加而增加。對多數(shù)機器 而言，乘法比加法更耗費時間，所以選取乘法為基本操作。 6 時間效率的度量 ?運行時間的度量： 接下來考慮運行時間的度量問題。例如，對于排序、 查找以及其他大多數(shù)與列表相關的問題來講，這個參數(shù)就是列表長度； 對于 n 次多項式求值問題，這個參數(shù)是多項式次數(shù)或者系數(shù)個數(shù)。 計算機 科學與技術 第 2章 算法效率分析基礎 ★ 算法效率分析框架 ★ 漸進符號和基本效率類型 ★ 非遞歸算法效率分析 ★ 遞歸算法效率分析 4 算法效率分析框架 ★ 算法效率分析框架 本節(jié)將概要地描述一個分析算法效率的一般性框架。例如： 1. 更大的數(shù)組排序需要花費更多的運行時間； 2. 更大的矩陣相乘需要花費更多的運算時間。 選擇輸入規(guī)模參數(shù)的合適量度，會受到算法操作細節(jié)的影響。所以， 用基本操作執(zhí)行 次數(shù)來作為時間效率的度量 。 n的一次、二次函數(shù)分別稱線性、二次增長率。 10 算法效率算例 ?算法的最優(yōu)、最差、平均效率 前述已知，我們用輸入規(guī)模 n 的函數(shù) T(n) 來度量算法的效率。 最優(yōu)效率 3. 若查找鍵位于表尾（最末元素）或不存在，該算法將 比較 n 次。（ 最差效率分析的價值 ） 順序查找： Cworse(n) = n 2 最優(yōu)效率： 當輸入規(guī)模為 n 時，算法在最優(yōu)情況下的效率。以后討論平均效率時 都引用其已知的推導結果。 13 順序查找算法的平均時間效率 ? 順序查找算法的平均時間效率： 假設： (1) 成功查找的概率是 p (0≤p≤1)，查找不成功的概率是 1 p； (2) 對任意第 i 次查找，第一次成功匹配（查找成功）發(fā)生在列表第 i 個 位置的概率相同，即查找鍵位于列表任一位置上的概率相同 1/n 。它統(tǒng)計不同用戶對某些字詞的使用率 （學習積累過程），來動態(tài)調(diào)整這些字詞下次出現(xiàn)的先后順序，高頻 先現(xiàn)，達到減少用戶翻閱時間的目的，提高了該算法的執(zhí)行效率。例如： 2 2 2( ) , 1 0 0 5 ( ) , 0 . 5 ( 1 ) ( )n O n n O n n n O n? ? ? ? ?3 2 3 2 4 2( ) , 0 . 0 0 0 0 1 ( ) , 1 ( )n O n n O n n n O n? ? ? ? ?16 上界符號 Ω(g(n)) ：增長次數(shù) 大于等于 g(n)（包括其常數(shù)倍， n 趨于無窮大）的 函數(shù)集合。舉例如下： 數(shù)組中特定元素的查找算法 ： 第一部分 ，用某種已知的排序算法對數(shù)組 排序，得到有序數(shù)組； 第二部分 ，對有序數(shù)組從頭至尾掃描，比較是否 與指定元素相等。1l ogl i m l i m 022l og1nnnnnnnenennnn? ? ? ?? ? ? ??? ? ?常 數(shù)羅 必 塔 法 則例 3： !2 nn比 較 和 的 增 長 次 數(shù) 。 n3 三次 一般來說，包含三重嵌套循環(huán)的算法。 輸出： A中最大元素的值 maxval←A[0] for i←1 to n1 do if A[i] maxval // 每次循環(huán)時無條件執(zhí)行（必執(zhí)行） maxval←A[i] // 每次循環(huán)時有條件執(zhí)行（不一定執(zhí)行） return maxval 效率分析框架要求明確輸入規(guī)模和基本操作。 因此有： ?非遞歸算法效率分析的通用方案： 1 確定 輸入規(guī)模 ； 2 確定 基本操作 ；（一般情況：它總是位于算法的最內(nèi)層循環(huán)里） 3 考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關。這里，我們研究其 最差效率 Cworst(n)。但考慮操作的時間耗費，對大多數(shù)計算機來講，乘法 比加法更費時間，且算術運算比賦值操作更費時間。另外方法，本例循環(huán)次數(shù)為： 2l o gbn? ???? ???? 向 上 取 整 ， 不 小 于 該 實 數(shù) 的 整 數(shù)/2n????2 b m axn?22l o g l (lo o g )gb nnn? ???????一點說明 ：考慮對數(shù)換底公式 l o g l o gl o g aab bnn?常 數(shù)因此，當我們分析增長率時，忽略對數(shù) 的底，簡單寫成 logn 32 遞歸算法效率分析 ★ 遞歸算法效率分析 ? 序列和遞推關系 ? 定義 ：數(shù)字序列是數(shù)字的一個有序列表。一個特定序列由初始條件（初值）確定。 2. 常系數(shù)： 遞推式中未知項系數(shù)為常數(shù)。 例 1：求齊次遞推方程通解和特解 解：該遞推方程的特征方程為： 特征方程有兩個相等的實根，根據(jù)定理 1，該遞推方程 通解 為： 根據(jù)初始條件解出待定常數(shù)，得到一個 特解 ： 12q q q??1 2 1 2( ) ( )n n nx n c q c n q c c n q? ? ? ?c1和 c2為待定常數(shù) ( ) 6 ( 1 ) 9 ( 2 ) 0( 0 ) 0 , ( 1 ) 3x n x n x nxx? ? ? ? ???22 126 9 0, ( 3 ) 0, 3q q q q q q? ? ? ? ? ? ? ?1 2 1 2( ) 3 3 ( ) 3n n nx n c c n c c n? ? ? ?c1和 c2為待定常數(shù) 01 2 111 2 20( 0) ( ( ) 330)3( 1 ) ( 1 )3 1nxc xnc nccx c c?? ? ? ? ??????? ? ?38 遞推方程求解：二階常系數(shù)線性遞推式例 2 例 2：求非齊次遞推方程滿足初始條件的特解 解： 根據(jù)例 1，該非齊次方程對應的 齊次方程的通解 為： 注意 ：此時不能代入初始條件解出 非齊次方程 的一個特解（為什么？） 現(xiàn)在，求 非齊次方程的一個特解 ： 設特解為 ，由遞推式解得 根據(jù)定理 2，得到 非齊次遞推方程的通解 ： (疊加 ) 據(jù)初始條件解出特解中待定常數(shù)，得特解： ( ) 6 ( 1 ) 9 ( 2 40)( 0 ) 0 , ( 1 ) 3x n x n x nxx? ? ? ? ????1 2 1 2( ) 3 3 ( ) 3n n nx n c c n c c n? ? ? ?c1和 c2為待定常數(shù) ()x n c? 6 9 4 1c c c c? ? ? ? ?12( ) 3 3 1nnx n ncc? ? ?c1和 c2為待定常數(shù) 001 2 1111 2 1 212( 0 ) 3 0 3 1 1 0( 1 ) 3 1 3 1 3 3 113 5 / 3x c c cc c cccxc? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?????5( ) 3 3 13nnx n n? ? ? ?39 遞推方程求解： k階常系數(shù)線性遞推式 公式法求解： k 階 常系數(shù)線性遞推式 （二階的推廣） 它的齊次遞推方程：方程右端項為 0，即 齊次方程的特征方程：（相同系數(shù)的一個 k 次方程，超越方程 ） 12( ) ( 1 ) ( (2) ( ))kx n x n xa a a f nn x n k? ? ?? ? ? ? ?( ) 0fn ?1 2 1 01 2 1 0k k k kkq a q a q a q a q?? ?? ? ? ? ? ?1212321 2 31121 2 3( ) ( 1 ) 0( ) ( 1 ) ( 2 ) 0( ) ( 1 ) (1:2:3:0020) ( 3 ) 0qaq a qx n a x nx n a x n a x nx n a x n a x naq a q aakkqxnak? ? ? ?? ? ? ? ? ?? ? ? ? ? ?????? ? ?? ? ?????數(shù)值解法 40 遞推方程求解： k階常系數(shù)線性遞推式（ 2） 求 k 階齊次遞推方程通解：定理 1推廣 （ 1）特征方程有 k 個不相等實根 qk ，齊次遞推方程通解為 ： （ 2） 特征方程有 r 個相等實根（重根），齊次遞推方程通解為 ： 說明： k 次特征方程有 k個實根 q1 , q2 ,... ,qk , 其中有 r 個實根相同。 。最后，根據(jù)給定 初始條件可得滿足初始條件的非齊次遞推方程特解。 4. 齊次： 方程右端為 0，即 f(n)=0。這就象對簡單的一元 方程 f(x) = 0 不能得到它的通解一樣。 自變量 n ： 表示一個元素在序列中的位置即序號； 函數(shù)值 x(n) ：表示該元素本身。 效率種類 ：因為本算例的基本操作數(shù)只與輸入規(guī)模有關，所以不必分別 研究最佳、最差和平均效率。 內(nèi)層 j 循環(huán)范圍： i+1, n1 建立增長 函數(shù) （基本操作執(zhí)行次數(shù)與輸入規(guī)模 n 的求和表達式）： ? ?? ?2 2 20 0 0220202122120( ) ( 1 )( 1 ) ( 1 ) 1( 1 ) 1