【正文】 若還與其他因數(shù) 有關(guān)（比如順序查找算法中基本操作執(zhí)行次數(shù)還與查找鍵在列表中的 位置有關(guān)），則按需要對 最差 、最佳、平均效率作出分析。 第一種情況 ：有兩個不相等實根 , 齊次遞推方程通解為 ： 12( ) ( 1 ) (2) )(aax n x n x n fn? ? ???2 12 0q a q a? ? ?12qq?1 1 2 2() nnx n c q c q??c1和 c2為待定常數(shù) 37 遞推方程求解：二階常系數(shù)線性遞推式例 1 第二種情況 ：有兩個相等實根 , 齊次遞推方程通解為 ： 第三種情況：特征方程在實數(shù)域無解。例子： 遞推式： ( ) ( 1 ,1( 0 ) 0)x nx nnnx? ? ???( 1 ) ( 2 ) ( 1 )( 2 ) ( 3 ) (( ) ( 1 )(2 2)( 1 )( ) ( 1 ) () ( 1 )( 3 ) ( 22 ) ()1)x n x nx n nxnn x nn k n kx n nn x n x n nnnnnnkx n? ? ????? ? ??? ? ? ?? ? ? ? ? ? ?? ? ? ??? ? ? ? ??? ? ? ? ??根據(jù)初始條件 (n=0)要求： n – k = 0, 上式變?yōu)椋? ( 0 ) 1 2 1( ) ( 1 )2x xnn n n? ? ? ? ? ??該法所得通項是直接由遞推式推出來的，故無需驗證。或 證明這樣一個序列不存在（遞推方程無解）。 算法 ： Binary(n) count←1 while n 1 do count←count + 1 n← return count 輸入規(guī)模 ：該正整數(shù)的大小 n ； 基本操作 ：選循環(huán)內(nèi)的除法操作。否則，選參與運(yùn)算的元素數(shù)。 2 2 11lg lgm m m m mi i i i i ii l i k i l i l i lmilmlnink k k k kinnni n i niinic a c a a b a bmli n n n n ni n nkaa a a a aai n n i? ? ? ? ????????????? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?? ? ? ? ???? ? ? ? ? ? ? ? ???? ? ? ? ???????2112 1 2 2 2 2 ( 1 ) 2 2ni n ninn??? ? ? ? ? ? ? ? ? ??27 例 2：元素唯一性問題 例 2： 【 元素唯一性問題 】 檢查給定數(shù)組的元素是否全部唯一 算法： UniqueElement ( A[0...n1] ) for i←0 to n2 do for j←i+1 to n1 do if A[ i ] = A[ j ] return false return true 輸入規(guī)模 ：數(shù)組元素個數(shù) n 基本操作 ：最內(nèi)層循環(huán)只有一個“比較”操作，選為基本操作。 25 非遞歸算法分析 2 接下來，效率分析框架要求我們找到基本操作與輸入規(guī)模的函數(shù)關(guān)系， 即增長函數(shù) T(n) 或者 C(n)。先從一個 簡單的算法開始，示范這類算法分析的步驟。 nlogn nlognn 諸多分治算法，包括合并排序和快速排序平均效率 屬于此類型。（或證明 : (n1)∈ Θ(n2)） 22220 . 5 ( 1 ) 1 1 1 1li m li m li m ( 1 )2 2 21( 1 ) ( )2n n nn n n nn n nn n n? ? ? ? ? ???? ? ? ?? ? ? ?22 利用極限比較增長率例 例 2： 2l o g nn比 較 和 的 增 長 次 數(shù) 。即存在正數(shù) c 和非負(fù)整數(shù) n0，使得下式成立： 3 2 3 2 4 2( ) , 0 . 0 0 0 0 1 ( ) , 1 ( )n n n n n n n? ? ? ? ? ? ? ?20 . 5 ( 1 ) ( )n n n? ? ?0 : ( ) ( )n n T n c g n??n0n()cg n()Tn規(guī)模 增長函數(shù) n0 之前情況無關(guān)緊要 上界 ( ) ( ( ) )T n O g n?最差效率分析 17 下界符號 證明： 證一： 據(jù)定義選?。? 證二： 據(jù)定義選?。? ?下屆符號 Ω 定義 ：把函數(shù) T(n)包含在 Ω(g(n))中， 記為 T(n)∈ Ω(g(n))；它成立的條件 是：對于足夠大的 n， T(n) 的下界 由 g(n)的常數(shù)倍決定。 T(n) 和 g(n) ：定義在自然數(shù)集合上的任意非負(fù)函數(shù)（ n取自然數(shù)）； T(n) ：算法的運(yùn)行時間函數(shù)（常用基本操作數(shù)增長函數(shù) C(n) 表示）； g(n) ：與增長函數(shù)作比較的函數(shù)。該做法與商業(yè)中 把固定資產(chǎn)成本按其使用年限攤銷到整個序列（各年）中的做法一致。 ? 平均效率分析的直接法 ： 1 將輸入分為幾種類型（可能的話），目的是使得對于同種輸入類型的 實例，具有相同的基本操作數(shù)。 12 平均效率 3 平均效率 無論是最優(yōu)還是最差效率，都不能提供這樣一種必要信息： 在隨機(jī)輸入 情況下，該算法具有怎樣的行為（時間耗費） 。 最差效率的確定 ：原理上講，首先對算法作一個分析，看看在規(guī)模 n 的 所有可能輸入中，那種輸入會導(dǎo)致基本操作數(shù) C(n) 達(dá)到最大值，計算 這個最差值 Cworse(n)。 【 算法 】 從列表頭開始，逐個 比較 列表中元素，直到發(fā)現(xiàn)匹配查找鍵的 元素或者到達(dá)列表尾為止（沒找到）。因此，我們最關(guān)心的就是函數(shù)的增長率，它決定了 算法的時間耗費（效率）。（時間耗費 T 為輸入規(guī)模 n 的函數(shù)） ? 分析框架的應(yīng)用 ： 設(shè) t 為算法的一個基本操作在特定機(jī)器上的執(zhí)行時間， C(n) 為該算法需 執(zhí)行的基本操作數(shù)。 鑒于此，希望找到一個不依賴于上述因素的時間度量。例如計算兩個 n 階矩陣的乘積，有兩種度量輸入規(guī)模的方法： 第一種方法：選擇矩陣的階 n ； 第二種方法：選擇參與乘法運(yùn)算的所有元素個數(shù)。 目前，隨著計算機(jī)硬件技術(shù)的飛速發(fā)展，空間效率已不是關(guān)心重點。 因此，我們主要關(guān)心的是時間效率。 第二種方法更具一般性，適用于非方陣。 問： 是否統(tǒng)計算法的 每步操作執(zhí)行次數(shù) 來作為算法的時間效率度量呢？ 答： 無此必要且較困難。用下式來估計該算法在該機(jī)器上的運(yùn)行時間： ( ) ( )T n t C n?忽略了非基本操作執(zhí)行時間 問： 為什么用約等于符號？ 8 分析框架的應(yīng)用例 ? 分析框架的應(yīng)用例： 根據(jù)上式，我們可以回答以下問題： 1 若某算法運(yùn)行在一臺比現(xiàn)在機(jī)器快 10倍的機(jī)器上，此算法運(yùn)行多快？ 答： 10倍。若輸入規(guī)模 n 很小，無論是高效的算法還是 低效的算法，時間耗費差距不明顯，所以算法分析針對大規(guī)模輸入。 【 分析 】 1. 很明顯，該算法的執(zhí)行效率與查找鍵在列表中的位置有密切關(guān)系。后面講到，通過確定 算法運(yùn)行時間的上界 ，分析 最壞情況為算法效率提供一個非常重要的信息。為此，引入 平均效率 。 2 得到或者假設(shè)各類輸入的概率分布，以推導(dǎo)出基本操作的平均次數(shù)。 通常，具備這種運(yùn)行特性的算法是在一定程度上的具有 “ 智能 ” 的算法， 通過 “ 學(xué)習(xí) ” 獲得 “ 知識 ” 累積，再運(yùn)用知識庫中的有關(guān)知識對算法下次 如何執(zhí)行提供指導(dǎo)，從而提高以后運(yùn)行的效率。 ?非正式介紹 O(g(n)) ：增長次數(shù) 小于等于 g(n)（包括其常數(shù)倍， n 趨于無窮大）的 函數(shù)集合。即存在正數(shù) c 和非負(fù)整數(shù) n0，使得下式成立： 21 0 0 5 ( )n O n??2( ) 1 0 0 5 1 0 0 ( 5 ) 1 0 1 1 0 1T n n n n n n n? ? ? ? ? ? ?當(dāng)220 ()101( ) ( ) , ( ),()5, g n nTncc g n T n O nn ?????證 畢2( ) 1 0 0 5 1 0 0 5 ( 1 ) 1 0 5 1 0 5T n n n n n n n? ? ? ? ? ? ?當(dāng)022( ) 1 0 0 5 , ( )105,( ) (1,) , ( ) ( )T n n g n nTnc g n T n O n? ? ?????證 畢n0n()cg n()Tn規(guī)模 增長函數(shù) n0 之前情況無關(guān)緊要 下界 ( ) ( ( ) )T n g n??最佳效率分析 0 : ( ) ( )n n T n c g n??18 同階符號 ?同階符號 Θ 定義 ：把函數(shù) T(n)包含在 Θ(g(n))中， 記為 T(n)∈ Θ(g(n))；它成立的條件 是：對于足夠大的 n， T(n) 的下界 和上界 均由 g(