【正文】 n)的常數(shù)倍決定。2222l og ( l og ) 39。 n2 二次 一般來說，包含兩重嵌套循環(huán)的算法。 例 1：從 n 個元素列表中查找最大值。這里， C(n) 是比較運算的次數(shù)。 效率種類 ：從循環(huán)結束條件可知，若比較的兩個元素相等，則提前結束 循環(huán)，返回“假”說明數(shù)組元素不唯一。 基本操作 ：最內(nèi)層循環(huán)有三種操作： 乘法、加法、賦值 。 效率種類 ：因基本操作執(zhí)行次數(shù)只與規(guī)模 n 有關，無需分別研究最佳、 最差和平均效率。如下遞推式的解： 驗證遞推方程 ：（代入法驗證） 驗證初始條件 ： 遞推方程的 通解 ：通常，有無窮多個序列（解）滿足同一個 遞推方程 ， 因此，通解一般包括若干任意常數(shù)。 36 遞推方程求解：二階常系數(shù)線性遞推式 ? 公式法 ：解二階常系數(shù)線性遞推方程 問題提出 ：有一類重要遞推式不能用前向和反向替換法求解。略。 4 建立基本操作數(shù)與規(guī)模的函數(shù)關系，即遞推關系和初始條件。 1. 當 f(n) 是 n 的 t 次多項式時，可設特解也是 n的多項式即特解形式 : 2. 當 f(n)是 n的指數(shù)函數(shù) , a,b為待定常數(shù)時，設特解形式： （ 1） b 不是相應齊次方程的 特征根 時 （ 2） b 是相應齊次方程的 e 重 特征根 時 1 1 01 2 1() tt ttx n p n p n p n p n? ?? ? ? ? ?0111221 2 30 : ( )1 : ( )2 : ( )t x n p n pt x n p n pt x n p n p n p? ? ?? ? ?? ? ? ?() nf n a b?() ,nx n c b c? 待 定p 為待定系數(shù) () ,en cx n c n b? 待 定42 遞推方程求解： k階常系數(shù)線性遞推式例 例：解遞歸方程 解： 1）求齊次遞推方程的特征根：（特征方程的根） 2）根據(jù)定理 1，兩個特征根不相等，齊次方程通解為： 3）求非齊次方程的一個任意特解： 因方程右端為 n的指數(shù)形式，且 b=4不是特征根，可設定特解形式： 將特解代入非齊次遞推方程： 4( ) 5 ( 1 ) 6 ( 2 )( 0 ) 04, ( 1 )20nx n x n x nxx? ? ? ? ? ??????2125 6 0 ( 2) ( 3) 02 , 3q q q qqq? ? ? ? ? ? ?? ? ? ? ?1 1 2 2 1 2( ) ( 2 ) ( 3 )n n n nx n c q c q c c? ? ? ? ? ?( ) 4 ,nnx n c b c c? ? ? ? 待 定12564 4 4 4 2 4n n n nc c c??? ? ? ? ? ? ?43 遞推方程求解： k階常系數(shù)線性遞推式例（續(xù)） 124 4 4 4 2 4564 4 4 424 1 61 0 3 2 14 2 4 2 1 6854868nnn n n nnnc c cc c cc c c c c??? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? 非齊次遞推方程的一個特解為： 4）非齊次遞推方程的通解：（定理 2） 2( ) 4 1 6 4 4n n nx n c ?? ? ? ? ?212( ) ( 2 ) ( 3 ) 4n n nx n c c ?? ? ? ? ?非 齊 次 特 解齊 次 通 解5）求滿足初始條件的非齊次遞推方程的解（特解）： 非齊次遞推方程的通解中代入初始條件 x(0)=0, x(1)=0 0 0 0 21 2 1 21 1 1 21 2 1 212( 0 ) ( 2 ) ( 3 ) 4 1 6 0( 1 ) ( 2 ) ( 3 ) 4 2 3 6 4 01 1 2 , 9 6x c c c cx c c c ccc???? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ??? ? ? ?2( ) 1 1 2 ( 2) 9 6 ( 3) 4n n nxn ?? ? ? ? ? ?47 遞推算法效率分析通用方案 ? 遞推算法效率分析通用方案（類似于非遞歸算法） 1 確定 輸入規(guī)模 ； 2 確定 基本操作 ；（規(guī)律：它總是位于算法的最內(nèi)層循環(huán)里） 3 考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關。 6. 特征方程：齊次遞推方程的解，取決于和遞推式具有相同系數(shù)的一個 二次方程即 特征方程 ： 定理 1：設 q1, q2 是特征方程的兩個根。例子如下： 遞推式： 根據(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 遞推方程求解：反向替換法 ? 反向替換法 ：（很有效）遞推方向： 前 ← 后 用遞推式將 x(n) 逐次表示為 x(n1), x(n2), x(n3), ..., x(nk), k=1, 2, 3, ... 然后通過運算化簡，得序列通項（解）。 ? 序列的兩種定義法 ： 1. 通項定義法：例如正偶數(shù)序列 2. 方程定義法：把序列的 通項 和 其他項 用方程定義，并規(guī)定序列的首項 或前幾項的值，例如： 0n?(1) 4x ?( ) 2 ( 1 ) , 0x n n n? ? ?( ) ( 1 ) , 1( 0 ) 0x n x n n nx? ? ? ??← 遞推方程或遞推關系，簡稱遞推式 ← 初始條件 33 解遞推方程的概念 ? 解遞推方程的概念 解遞推方程，意味著找到序列 通項 ，既滿足遞推式又滿足初始條件。 建立增長 函數(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。本例均為 n1 30 例 3： 【 矩陣乘法 】 時間效率分析（續(xù)） 輸入規(guī)模 ：因是方陣，選擇矩陣的階 n 。 11( ) 1 ()1niC n n n??? ?????結論 ：本算法具有線性增長率 26 復習：幾個常用求和公式 ?復習：幾個常用求和公式 12211111 2 1001()1 1 1 1 1111 2 ( 1 ) ( )22112111 ( 1 ) 。 本算法每個數(shù)組元素都要進行一次比較，故不區(qū)分最優(yōu)、最差和平均效率。 24 非遞歸算法分析 ★ 非遞歸算法的效率分析（很常用） 本節(jié)將系統(tǒng)地運用前節(jié)的通用框架來分析非遞歸算法的效率。 n 線性 掃描規(guī)模為 n的列表（如順序查找）算法。 : ( ) ( ( ) ) (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的增長率。例如： ?上界符號 O （最常用） 定義 ：把函數(shù) T(n)包含在 O(g(n))中， 記為 T(n)∈ O(g(n))；它成立的條件 是：對于足夠大的 n， T(n) 的上界 由 g(n)的常數(shù)倍決定。為了對增長函數(shù)作出 比較和歸類，通常使用三種符號： O,Ω,Θ(theta). 下面就這些符號先作一個非正式介紹（便于理解）。 我們知道，在有些情況下單次運行的時間代價可能比較昂貴，但 n 次 運行的 總時間花費明顯低于單次運行的最差效率乘以 n ，因此我們把 最差效率的高成本攤到各次運行中去，即攤銷效率。顯然，我們 不能通過求最優(yōu)和最差效率平均值的方法來求平