【正文】 ? ? ?????數(shù)值解法 40 遞推方程求解： k階常系數(shù)線性遞推式（ 2） 求 k 階齊次遞推方程通解：定理 1推廣 （ 1）特征方程有 k 個不相等實根 qk ，齊次遞推方程通解為 ： （ 2） 特征方程有 r 個相等實根（重根），齊次遞推方程通解為 ： 說明： k 次特征方程有 k個實根 q1 , q2 ,... ,qk , 其中有 r 個實根相同。一個特定序列由初始條件（初值）確定。但考慮操作的時間耗費，對大多數(shù)計算機來講，乘法 比加法更費時間，且算術運算比賦值操作更費時間。 因此有： ?非遞歸算法效率分析的通用方案： 1 確定 輸入規(guī)模 ； 2 確定 基本操作 ；（一般情況：它總是位于算法的最內(nèi)層循環(huán)里） 3 考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關。 n3 三次 一般來說，包含三重嵌套循環(huán)的算法。舉例如下： 數(shù)組中特定元素的查找算法 ： 第一部分 ，用某種已知的排序算法對數(shù)組 排序，得到有序數(shù)組； 第二部分 ，對有序數(shù)組從頭至尾掃描，比較是否 與指定元素相等。它統(tǒng)計不同用戶對某些字詞的使用率 （學習積累過程），來動態(tài)調整這些字詞下次出現(xiàn)的先后順序，高頻 先現(xiàn)，達到減少用戶翻閱時間的目的，提高了該算法的執(zhí)行效率。以后討論平均效率時 都引用其已知的推導結果。 最優(yōu)效率 3. 若查找鍵位于表尾（最末元素）或不存在，該算法將 比較 n 次。 n的一次、二次函數(shù)分別稱線性、二次增長率。 選擇輸入規(guī)模參數(shù)的合適量度，會受到算法操作細節(jié)的影響。 計算機 科學與技術 第 2章 算法效率分析基礎 ★ 算法效率分析框架 ★ 漸進符號和基本效率類型 ★ 非遞歸算法效率分析 ★ 遞歸算法效率分析 4 算法效率分析框架 ★ 算法效率分析框架 本節(jié)將概要地描述一個分析算法效率的一般性框架。 6 時間效率的度量 ?運行時間的度量： 接下來考慮運行時間的度量問題。 T(n) 隨著 n 次數(shù)的增加而增加。 11 最優(yōu)、最差效率 1 最差效率 ： （最為關注） 當輸入規(guī)模為 n 時，算法在最壞情況下的效率。 所以 如果沒有平均效率分析的話，我們會錯失不少重要的算法。 15 漸進符號 ★ 漸進符號和基本效率類型 上節(jié)指出，效率分析主要關心的是一個算法的 基本操作數(shù)隨問題規(guī)模的 增長率 （增長次數(shù)），即問題規(guī)模 n 變大情況下，該算法的基本操作數(shù) 增長的快慢（它是規(guī)模 n 的函數(shù) ——增長函數(shù)）。它根據(jù)極限定義， 對兩個函數(shù)的比值求極限，以判定哪個函數(shù)增長更快。 n! 階乘 求 n個元素集合的完全排列的算法。 5 利用運算公式（法則），確定該增長函數(shù)的增長率。就是一種 時間效率 。 ? 前向替換法 ：遞推方向： 前 → 后 從序列 首項 （由初始條件給出）開始，使用遞推式生成序列的 前幾項 ， 希望通過對前幾項的觀察找到序列的 通項 ，并進行驗證。 對一般的非齊次遞推方程，不存在尋找特解的通用方法，只能用觀察法 去假定特解的形式，然后用待定系數(shù)法確定系數(shù)。 定理 2： 把非齊次方程的特解和相應的齊次方程通解相加，得到該 非齊次 方程的通解 。本例 遞推方程的 特解 ：滿足遞推方程的一個特定的序列（解），通常是那個 滿足初始條件的特解。每次循環(huán)時， 每種操作均被執(zhí)行一次，所以任選一種作為基本操作均可，因為它們的 執(zhí)行次數(shù)都一樣。不難看出， 本算法每循環(huán)一次，基本操作就要執(zhí)行一次。 n 階方陣的 某些特定算法。即 存在正數(shù) c 和非負整數(shù) n0，使得： 例：證明 證：注意到 上界情況： 下界情況： 0 1 2: ( ) ( ) ( )n n c g n T n c g n? ? ?n0n1 ()c g n()Tn規(guī)模 增長函數(shù) n0 之前情況無關緊要 ( ) ( ( ) )T n g n??2 ()c g n20 . 5 ( 1 ) ( )n n n? ? ?2 2 2 ( 1 ) ()n n n n n c On n? ? ? ? ??22222100 . 5 ( 1 ) 0 . 5 0 . 50 . 5 0 . 5 ( 2 )0 . 2 5 (.5)nn n n nn n w h i l e nn nnc???????????0n?1200 . 2 5 , 0 . 52ccn???19 漸進符號的有用性質 ?漸進符號的有用性質（ 3 證明從略） 性質 1： 性質 2： 性質 3： 性質 4： 性質 4的價值 ：（證明見下頁） 某些算法是由兩個（以上）執(zhí)行部分組成，性質 4指明：該算法的整體 效率由具有較大增長率的部分決定，即它效率最差的部分。一個例子：漢字拼音 輸入法中的動態(tài)詞頻調整算法。 平均效率分析要比最差和最優(yōu)效率分析困難很多。 2. 若查找鍵位于表頭（第一個元素），該算法只 比較 一次。（ t 增加 10倍， C(n)不變） 2 設 ，若輸入規(guī)模翻倍，該算法運行時間如何變化？ 1( ) ( 1 )2C n n n??( ) ( )T n t C n?221 1 1 1( ) ( 1 )2 2 2 2C n n n n nn? ? ? ? ? （ n 不是太小如 n = 100） 221( 2 )( 2 ) ( 2 )2 ()1( ) (4)2nT n t C nT n t C n n? ? ? ? 倍不考慮每個操作步在機器上具體的執(zhí)行時間 t ，則時間耗費即為： ( ) ( )T n C n? 時間耗費即為基本操作數(shù)，為輸入規(guī)模 n的函數(shù)。 對于選擇不同的輸入規(guī)模，其算法效率在含義上有所差別。 時間效率 指出算法運行得有多快； 空間效率 關心算法需要的額外空間。我們?yōu)楹尾贿x擇時間的標準度量單位 （秒、毫秒等）來度量算法的運行時間呢？其 理由 如下： 1. 它依賴于特定計算機的運行速度； 2. 它依賴于實現(xiàn)算法的代碼質量；（程序員編程的水平問題） 3. 它依賴于編譯器的好壞；（編譯成機器碼的質量，即指令條數(shù)） 4. 它還依賴于一些其他問題如操作系統(tǒng)的調度策略等。函數(shù)值 T(n) 增加快慢，決定于這個增長函數(shù)特性； 也就是說，線性增長函數(shù)的函數(shù)值增加較慢，二次增長函數(shù)增加較快， 指數(shù)增長函數(shù)最快。此時，相對于其他規(guī)模 為 n 的輸入，該算法運行時間最長（最慢）。顯然，我們 不能通過求最優(yōu)和最差效率平均值的方法來求平均效率。為了對增長函數(shù)作出 比較和歸類，通常使用三種符號： O,Ω,Θ(theta). 下面就這些符號先作一個非正式介紹（便于理解）。 : ( ) ( ( ) ) (0() ( ): ( ) ( ( ) ) ( ) ( ): ( ) ( ( ) ) ()l) ) ( )im(nT n O g n T n g nT n g n TcTn n g nT n g n T n g ngn????????????????比 增 長 慢與 增 長 相 同比 增 長 快不 存 在 : 該 法 不 適 用例 1：比較 (n1)和 n2的增長率。 24 非遞歸算法分析 ★ 非遞歸算法的效率分析（很常用） 本節(jié)將系統(tǒng)地運用前節(jié)的通用框架來分析非遞歸算法的效率。 11( ) 1 ()1niC n n n??? ?????結論 ：本算法具有線性增長率 26 復習：幾個常用求和公式 ?復習：幾個常用求和公式 12211111 2 1001()1 1 1 1 1111 2 ( 1 ) ( )22112111 ( 1 ) 。 建立增長 函數(shù) （基本操作數(shù)與輸入規(guī)模 n 的求和表達式） ： 1 1 1 1 1 10 0 0 0 0 0112 3120030( ) 11 )1(n n n n n ni j i j i jnnkniinCnnnnnn? ? ? ? ? ?? ? ? ? ??? ???????? ? ? ????? ? ? ??? ? ? ? ? ????31 例 4： 【 二進制位數(shù) 】 一個十進制正整數(shù)的二進制位數(shù) 例 4： 【 二進制位數(shù) 】 一個十進制正整數(shù) n 的二進制位數(shù) b。例子如下： 遞推式： 根據(jù)初始條件和遞推式，生成序列前幾項： ( ) 2 ( 1 ) 1 , 1( 1 ) 1x n x n nx? ? ? ??( 1 ) 1( 2 ) 2 ( 1 ) 1 2 1 1 3( 3 ) 2 ( 2 ) 1 2 3 1 7( 4 ) 2 ( 3 ) 1 2 7 1 1 5( 5 ) 2 ( 4 ) 1 2 1 5 1 3 1xxxxxxxxx?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ?(1 0) ,2 nxn n?? ?12 ( 1 ) 12 ( 2 1 ) 12 2 1 ( )nnxnxn?? ? ?? ? ?? ? ? ??右 端左 端驗證： 代入法 方法評價：有時候很難從序列前幾項中找到通項！ 漢諾 (hanoi)塔游戲 35 遞推方程求解：反向替換法 ? 反向替換法 ：（很有效）