《算法效率分析基礎》PPT課件.ppt

算法設計與分析計算機與信息學院 2 使用教材 使用教材 作者 美 AnanyLevitin譯者 潘彥出版社 清華大學叢書名 國外經(jīng)典教材 計算機科學與技術 第2章算法效率分析基礎 算法效率分析框架漸進符號和基本效率類型非遞歸算法效率分析遞歸算法效率分析 4 算法效率分析框架 算法效率分析框架本節(jié)將概要地描述一個分析算法效率的一般性框架 時間效率指出算法運行得有多快 空間效率關心算法需要的額外空間 目前 隨著計算機硬件技術的飛速發(fā)展 空間效率已不是關心重點 因此 我們主要關心的是時間效率 輸入規(guī)模的度量 問題規(guī)模 一個顯而易見的事實 幾乎所有的算法 對于更大規(guī)模輸入都需要運行更長的時間 即算法耗費的時間隨著輸入規(guī)模的增大而增加 例如 1 更大的數(shù)組排序需要花費更多的運行時間 2 更大的矩陣相乘需要花費更多的運算時間 因此 采用一個以算法輸入規(guī)模n為參數(shù)的函數(shù) 來研究算法效率就是非常合乎邏輯的 輸入規(guī)模的選擇問題 在大多數(shù)情況下 選擇這樣一個參數(shù)是非常直接的 例如 對于排序 查找以及其他大多數(shù)與列表相關的問題來講 這個參數(shù)就是列表長度 對于n次多項式求值問題 這個參數(shù)是多項式次數(shù)或者系數(shù)個數(shù) 5 輸入規(guī)模的選擇 當然 有些情況下 怎樣選擇輸入規(guī)模參數(shù)是有差別的 例如計算兩個n階矩陣的乘積 有兩種度量輸入規(guī)模的方法 第一種方法 選擇矩陣的階n 第二種方法 選擇參與乘法運算的所有元素個數(shù) 第二種方法更具一般性 適用于非方陣 對于選擇不同的輸入規(guī)模 其算法效率在含義上有所差別 選擇輸入規(guī)模參數(shù)的合適量度 會受到算法操作細節(jié)的影響 例如 對于一個檢查文字拼寫的算法 如果算法要求對每個字符都要檢查 那么應該用字符數(shù)作為輸入規(guī)模度量 如果算法操作的是單詞 那么選擇單詞數(shù)作為輸入規(guī)模的度量 若算法與數(shù)字特性 數(shù)字的大小 相關 那么在度量它的輸入規(guī)模時 計算機科學家傾向于選擇數(shù)字的二進制位數(shù)作為輸入規(guī)模的度量 6 時間效率的度量 運行時間的度量 接下來考慮運行時間的度量問題 我們?yōu)楹尾贿x擇時間的標準度量單位 秒 毫秒等 來度量算法的運行時間呢 其理由如下 1 它依賴于特定計算機的運行速度 2 它依賴于實現(xiàn)算法的代碼質量 程序員編程的水平問題 3 它依賴于編譯器的好壞 編譯成機器碼的質量 即指令條數(shù) 4 它還依賴于一些其他問題如操作系統(tǒng)的調度策略等 鑒于此 希望找到一個不依賴于上述因素的時間度量 問 是否統(tǒng)計算法的每步操作執(zhí)行次數(shù)來作為算法的時間效率度量呢 答 無此必要且較困難 一個算法中有許多操作 決定算法時間效率的是那些很耗費時間的操作步 因此只需關心這些操作即可評價一個算法時間效率 這些最關鍵的操作步稱為基本操作 它們對算法執(zhí)行時間的占用最大 基本操作即算法中最費時的操作 所以 用基本操作執(zhí)行次數(shù)來作為時間效率的度量 7 基本操作的選取 基本操作的選取例 大多數(shù)排序算法是通過比較排序元素 鍵 來進行工作 因此它的基本操作應選為鍵的比較操作 即算法中鍵的比較次數(shù) 矩陣乘法 或多項式運算 需完成兩種操作 乘法和加法 對多數(shù)機器而言 乘法比加法更耗費時間 所以選取乘法為基本操作 在定義了算法的輸入規(guī)模n和基本操作后 我們就可以建立起一個算法時間效率的分析框架 對規(guī)模為n的算法 通過統(tǒng)計其基本操作的執(zhí)行次數(shù)來度量算法的時間效率 時間耗費T為輸入規(guī)模n的函數(shù) 分析框架的應用 設t為算法的一個基本操作在特定機器上的執(zhí)行時間 C n 為該算法需執(zhí)行的基本操作數(shù) 用下式來估計該算法在該機器上的運行時間 忽略了非基本操作執(zhí)行時間 問 為什么用約等于符號 8 分析框架的應用例 分析框架的應用例 根據(jù)上式 我們可以回答以下問題 1若某算法運行在一臺比現(xiàn)在機器快10倍的機器上 此算法運行多快 答 10倍 t增加10倍 C n 不變 2設 若輸入規(guī)模翻倍 該算法運行時間如何變化 n不是太小如n 100 不考慮每個操作步在機器上具體的執(zhí)行時間t 則時間耗費即為 時間耗費即為基本操作數(shù) 為輸入規(guī)模n的函數(shù) n的一次 二次函數(shù)分別稱線性 二次增長率 2n稱指數(shù)增長率 9 增長次數(shù) 增長率 增長次數(shù) 增長率 基本操作數(shù) 時間耗費 是輸入規(guī)模n的函數(shù) 記為T n T n 隨著n次數(shù)的增加而增加 函數(shù)值T n 增加快慢 決定于這個增長函數(shù)特性 也就是說 線性增長函數(shù)的函數(shù)值增加較慢 二次增長函數(shù)增加較快 指數(shù)增長函數(shù)最快 因此 我們最關心的就是函數(shù)的增長率 它決定了算法的時間耗費 效率 若輸入規(guī)模n很小 無論是高效的算法還是低效的算法 時間耗費差距不明顯 所以算法分析針對大規(guī)模輸入 增長函數(shù)表 對于算法分析具有重要意義的函數(shù)值 近似值 10 算法效率算例 算法的最優(yōu) 最差 平均效率前述已知 我們用輸入規(guī)模n的函數(shù)T n 來度量算法的效率 若T n 隨n增長快 則算法效率較差 若T n 隨n增長較慢 則算法效率更好 這里 沒考慮算法效率與特定輸入的關系 諸多算法的效率不僅與規(guī)模有關 且與特定的輸入有關 下面以順序查找算法為例 名稱 順序查找 要求 在列表中查找一次給定項 查找鍵 該列表有n個元素 算法 從列表頭開始 逐個比較列表中元素 直到發(fā)現(xiàn)匹配查找鍵的元素或者到達列表尾為止 沒找到 分析 1 很明顯 該算法的執(zhí)行效率與查找鍵在列表中的位置有密切關系 2 若查找鍵位于表頭 第一個元素 該算法只比較一次 最優(yōu)效率3 若查找鍵位于表尾 最末元素 或不存在 該算法將比較n次 最差4 若查找鍵位于表中間 該算法比較次數(shù)不固定 平均效率 通過上述例子 引入最佳 最差和平均效率的概念 11 最優(yōu) 最差效率 1最差效率 最為關注 當輸入規(guī)模為n時 算法在最壞情況下的效率 此時 相對于其他規(guī)模為n的輸入 該算法運行時間最長 最慢 最差效率的確定 原理上講 首先對算法作一個分析 看看在規(guī)模n的所有可能輸入中 那種輸入會導致基本操作數(shù)C n 達到最大值 計算這個最差值Cworse n 后面講到 通過確定算法運行時間的上界 分析最壞情況為算法效率提供一個非常重要的信息 也即 對于任何規(guī)模n的實例來講 它保證算法運行時間不會超過最壞輸入情況下的運行時間 Cworse n 最差效率分析的價值 順序查找 Cworse n n2最優(yōu)效率 當輸入規(guī)模為n時 算法在最優(yōu)情況下的效率 此時 相對于其他規(guī)模為n的輸入 該算法運行時間最短 最快 順序查找 Cbest n 1最優(yōu)效率分析的價值 遠不如最差效率分析重要 因不能指望每次輸入都是最優(yōu)輸入 但它對算法的的選擇有指導意義 例如 某算法在有序列表情況下效率很高 對于基本有序的輸入數(shù)據(jù) 該算法可以獲得接近最優(yōu)輸入的效率 實際中可考慮選擇該算法 重要的是 如果一個算法的最優(yōu)效率都不能滿足實際需要 可立即拋棄該算法 12 平均效率 3平均效率無論是最優(yōu)還是最差效率 都不能提供這樣一種必要信息 在隨機輸入情況下 該算法具有怎樣的行為 時間耗費 為此 引入平均效率 平均效率分析要比最差和最優(yōu)效率分析困難很多 以后討論平均效率時都引用其已知的推導結果 對推導有興趣的同學 請查閱有關書籍 平均效率分析的價值 有許多重要算法的平均效率比它們過于悲觀的最差效率要好很多 所以如果沒有平均效率分析的話 我們會錯失不少重要的算法 顯然 我們不能通過求最優(yōu)和最差效率平均值的方法來求平均效率 平均效率分析的直接法 1將輸入分為幾種類型 可能的話 目的是使得對于同種輸入類型的實例 具有相同的基本操作數(shù) 2得到或者假設各類輸入的概率分布 以推導出基本操作的平均次數(shù) 但各類輸入的概率模型往往又難以驗證 雖然它可能很合理 13 順序查找算法的平均時間效率 順序查找算法的平均時間效率 假設 1 成功查找的概率是p 0 p 1 查找不成功的概率是1 p 2 對任意第i次查找 第一次成功匹配 查找成功 發(fā)生在列表第i個位置的概率相同 即查找鍵位于列表任一位置上的概率相同1 n 基于假設 在列表任一位置上查找成功的概率為p 1 n 甚至可進一步假設p 0 5 若查找成功的位置為i 算法做的比較次數(shù) 基本操作 為i次 考慮成功查找概率 比較次數(shù)為p i n 若查找不成功 算法做的比較次數(shù)為n 列表全部查找一遍 考慮不成功查找概率 比較次數(shù)則為n 1 p 因此 算法平均效率 統(tǒng)計平均 14 攤銷效率 4攤銷效率它并不適合于算法的單次運行 而應用于算法對同樣數(shù)據(jù)的多次運行 我們知道 在有些情況下單次運行的時間代價可能比較昂貴 但n次運行的總時間花費明顯低于單次運行的最差效率乘以n 因此我們把最差效率的高成本攤到各次運行中去 即攤銷效率 該做法與商業(yè)中把固定資產(chǎn)成本按其使用年限攤銷到整個序列 各年 中的做法一致 通常 具備這種運行特性的算法是在一定程度上的具有 智能 的算法 通過 學習 獲得 知識 累積 再運用知識庫中的有關知識對算法下次如何執(zhí)行提供指導 從而提高以后運行的效率 一個例子 漢字拼音輸入法中的動態(tài)詞頻調整算法 它統(tǒng)計不同用戶對某些字詞的使用率 學習積累過程 來動態(tài)調整這些字詞下次出現(xiàn)的先后順序 高頻先現(xiàn) 達到減少用戶翻閱時間的目的 提高了該算法的執(zhí)行效率 后續(xù)章節(jié)中 除非專門說明 都將最差情況下時間耗費的極限作為算法的時間耗費 稱時間復雜性或時間效率 求解過程稱為時間漸進分析 15 漸進符號 漸進符號和基本效率類型上節(jié)指出 效率分析主要關心的是一個算法的基本操作數(shù)隨問題規(guī)模的增長率 增長次數(shù) 即問題規(guī)模n變大情況下 該算法的基本操作數(shù)增長的快慢 它是規(guī)模n的函數(shù) 增長函數(shù) 為了對增長函數(shù)作出比較和歸類 通常使用三種符號 O theta 下面就這些符號先作一個非正式介紹 便于理解 T n 和g n 定義在自然數(shù)集合上的任意非負函數(shù) n取自然數(shù) T n 算法的運行時間函數(shù) 常用基本操作數(shù)增長函數(shù)C n 表示 g n 與增長函數(shù)作比較的函數(shù) 非正式介紹O g n 增長次數(shù)小于等于g n 包括其常數(shù)倍 n趨于無窮大 的函數(shù)集合 即g n 是增長函數(shù)集的上界 例如 16 上界符號 g n 增長次數(shù)大于等于g n 包括其常數(shù)倍 n趨于無窮大 的函數(shù)集合 即g n 是增長函數(shù)集的下界 例如 g n 增長次數(shù)等于g n 包括其常數(shù)倍 n趨于無窮大 的函數(shù)集合 即g n 與增長函數(shù)集同階 相同的增長率 例如 上界符號O 最常用 定義 把函數(shù)T n 包含在O g n 中 記為T n O g n 它成立的條件是 對于足夠大的n T n 的上界由g n 的常數(shù)倍決定 即存在正數(shù)c和非負整數(shù)n0 使得下式成立 17 下界符號 證明 證一 據(jù)定義選取 證二 據(jù)定義選取 下屆符號 定義 把函數(shù)T n 包含在 g n 中 記為T n g n 它成立的條件是 對于足夠大的n T n 的下界由g n 的常數(shù)倍決定 即存在正數(shù)c和非負整數(shù)n0 使得下式成立 規(guī)模 增長函數(shù) n0之前情況無關緊要 下界 最佳效率分析 18 同階符號 同階符號 定義 把函數(shù)T n 包含在 g n 中 記為T n g n 它成立的條件是 對于足夠大的n T n 的下界和上界均由g n 的常數(shù)倍決定 即存在正數(shù)c和非負整數(shù)n0 使得 例 證明證 注意到上界情況 下界情況 19 漸進符號的有用性質 漸進符號的有用性質 1 2 3證明從略 性質1 性質2 性質3 性質4 性質4的價值 證明見下頁 某些算法是由兩個 以上 執(zhí)行部分組成 性質4指明 該算法的整體效率由具有較大增長率的部分決定 即它效率最差的部分 舉例如下 數(shù)組中特定元素的查找算法 第一部分 用某種已知的排序算法對數(shù)組排序 得到有序數(shù)組 第二部分 對有序數(shù)組從頭至尾掃描 比較是否與指定元素相等 若排序部分增長函數(shù)為0 5n n 1 O n2 第二部分的增長函數(shù)為n O n 那么 算法的整體效率為T n O n2 20 漸進符號性質4的證明 性質4的證明 21 利用極限比較增長率 利用極限比較增長率 此法常用來比較兩個特定增長函數(shù)的增長率 簡便 它根據(jù)極限定義 對兩個函數(shù)的比值求極限 以判定哪個函數(shù)增長更快 例1 比較0 5n n 1 和n2的增長率 或證明 0 5n n 1 n2 22 利用極限比較增長率例 例2 例3 23 漸進效率的基本類型 漸進效率的基本類型 24 非遞歸算法分析 非遞歸算法的效率分析 很常用 本節(jié)將系統(tǒng)地運用前節(jié)的通用框架來分析非遞歸算法的效率 先從一個簡單的算法開始 示范這類算法分析的步驟 例1 從n個元素列表中查找最大值 用數(shù)組簡單實現(xiàn)列表 算法MaxElement A 0 n 1 求數(shù)組A中元素的最大值 輸入 實數(shù)數(shù)組A 輸出 A中最大元素的值maxval A 0 fori 1ton 1doifA i maxval 每次循環(huán)時無條件執(zhí)行 必執(zhí)行 maxval A i 每次循環(huán)時有條件執(zhí)行 不一定執(zhí)行 returnmaxval效率分析框架要求明確輸入規(guī)模和基本操作 輸入規(guī)模 數(shù)組元素的個數(shù)n 基本操作 根據(jù)基本操作概念 它應該是算法中最費時的操作 因此 應該選擇for循環(huán)內的比較操作 本算法每個數(shù)組元素都要進行一次比較 故不區(qū)分最優(yōu) 最差和平均效率 25 非遞歸算法分析2 接下來 效率分析框架要求我們找到基本操作與輸入規(guī)模的函數(shù)關系 即增長函數(shù)T n 或者C n 這里 C n 是比較運算的次數(shù) 不難看出 本算法每循環(huán)一次 基本操作就要執(zhí)行一次 因此有 非遞歸算法效率分析的通用方案 1確定輸入規(guī)模 2確定基本操作 一般情況 它總是位于算法的最內層循環(huán)里 3考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關 若還與其他因數(shù)有關 比如順序查找算法中基本操作執(zhí)行次數(shù)還與查找鍵在列表中的位置有關 則按需要對最差 最佳 平均效率作出分析 4建立基本操作執(zhí)行次數(shù)與輸入規(guī)模n的求和表達式 即增長函數(shù) 5利用運算公式 法則 確定該增長函數(shù)的增長率 結論 本算法具有線性增長率 26 復習 幾個常用求和公式 復習 幾個常用求和公式 27 例2 元素唯一性問題 例2 元素唯一性問題 檢查給定數(shù)組的元素是否全部唯一算法 UniqueElement A 0 n 1 fori 0ton 2doforj i 1ton 1doifA i A j returnfalsereturntrue輸入規(guī)模 數(shù)組元素個數(shù)n基本操作 最內層循環(huán)只有一個 比較 操作 選為基本操作 效率種類 從循環(huán)結束條件可知 若比較的兩個元素相等 則提前結束循環(huán) 返回 假 說明數(shù)組元素不唯一 最佳的情況是 首次比較就結束循環(huán) 即數(shù)組開始兩個元素就相同 最差的情況是 循環(huán)結束前的最后一次比較才發(fā)現(xiàn)相同的元素 最后兩個 或者該數(shù)組沒有相同元素 都要完成全部循環(huán)次數(shù) 即比較次數(shù)就是循環(huán)次數(shù) 這里 我們研究其最差效率Cworst n i j 28 例2 元素唯一性問題 續(xù) 外層i循環(huán)范圍 0 n 2 內層j循環(huán)范圍 i 1 n 1建立增長函數(shù) 基本操作執(zhí)行次數(shù)與輸入規(guī)模n的求和表達式 29 例3 矩陣乘法 時間效率分析 例3 矩陣乘法 時間效率分析給定兩個方陣A和B 根據(jù)矩陣乘法定義計算它們之乘積 算法 MatrixMultiplication A 0 n 1 0 n 1 B 0 n 1 0 n 1 fori 0ton 1do 行循環(huán)forj 0ton 1do 列循環(huán)M i j 0 0 初始化fork 0ton 1do 用變量k表示變化的腳標M i j M i j A i k B k j returnM 列 行 如果是非方陣 只需改變行列循環(huán)變量的范圍即可 本例均為n 1 30 例3 矩陣乘法 時間效率分析 續(xù) 輸入規(guī)模 因是方陣 選擇矩陣的階n 否則 選參與運算的元素數(shù) 基本操作 最內層循環(huán)有三種操作 乘法 加法 賦值 每次循環(huán)時 每種操作均被執(zhí)行一次 所以任選一種作為基本操作均可 因為它們的執(zhí)行次數(shù)都一樣 但考慮操作的時間耗費 對大多數(shù)計算機來講 乘法比加法更費時間 且算術運算比賦值操作更費時間 所以 本例選乘法作為基本操作 效率種類 因為本算例的基本操作數(shù)只與輸入規(guī)模有關 所以不必分別研究最佳 最差和平均效率 就是一種時間效率 建立增長函數(shù) 基本操作數(shù)與輸入規(guī)模n的求和表達式 31 例4 二進制位數(shù) 一個十進制正整數(shù)的二進制位數(shù) 例4 二進制位數(shù) 一個十進制正整數(shù)n的二進制位數(shù)b 算法 Binary n count 1whilen 1docount count 1n returncount輸入規(guī)模 該正整數(shù)的大小n 基本操作 選循環(huán)內的除法操作 效率種類 因基本操作執(zhí)行次數(shù)只與規(guī)模n有關 無需分別研究最佳 最差和平均效率 增長函數(shù) 本例基本操作增長函數(shù)不是一個求和表達式 需要用其他的方法來計算循環(huán)次數(shù) 基本操作執(zhí)行次數(shù) 可建立遞推式來求解 后面兩節(jié)介紹 另外方法 本例循環(huán)次數(shù)為 32 遞歸算法效率分析 遞歸算法效率分析序列和遞推關系定義 數(shù)字序列是數(shù)字的一個有序列表 例如 2 4 6 8 10 12 正偶數(shù)序列 0 1 1 2 3 5 8 裴波拉契數(shù)序列 序列的函數(shù)表示法 x n 把序列表示為一個函數(shù) 自變量n 表示一個元素在序列中的位置即序號 函數(shù)值x n 表示該元素本身 如正偶數(shù)序列第2個元素 x n 稱為該序列的通項 序列的兩種定義法 1 通項定義法 例如正偶數(shù)序列2 方程定義法 把序列的通項和其他項用方程定義 并規(guī)定序列的首項或前幾項的值 例如 遞推方程或遞推關系 簡稱遞推式 初始條件 33 解遞推方程的概念 解遞推方程的概念解遞推方程 意味著找到序列通項 既滿足遞推式又滿足初始條件 或證明這樣一個序列不存在 遞推方程無解 如下遞推式的解 驗證遞推方程 代入法驗證 驗證初始條件 遞推方程的通解 通常 有無窮多個序列 解 滿足同一個遞推方程 因此 通解一般包括若干任意常數(shù) 本例遞推方程的特解 滿足遞推方程的一個特定的序列 解 通常是那個滿足初始條件的特解 一個特定序列由初始條件 初值 確定 不包括初始條件 34 遞推方程求解 前向替換法 遞推方程的求解方法不存在對每一個遞推方程都有效的一種通用方法 這就象對簡單的一元方程f x 0不能得到它的通解一樣 前向替換法 遞推方向 前 后從序列首項 由初始條件給出 開始 使用遞推式生成序列的前幾項 希望通過對前幾項的觀察找到序列的通項 并進行驗證 例子如下 遞推式 根據(jù)初始條件和遞推式 生成序列前幾項 通項 方法評價 有時候很難從序列前幾項中找到通項 漢諾 hanoi 塔游戲 35 遞推方程求解 反向替換法 反向替換法 很有效 遞推方向 前 后用遞推式將x n 逐次表示為x n 1 x n 2 x n 3 x n k k 1 2 3 然后通過運算化簡 得序列通項 解 例子 遞推式 根據(jù)初始條件 n 0 要求 n k 0 上式變?yōu)?該法所得通項是直接由遞推式推出來的 故無需驗證 36 遞推方程求解 二階常系數(shù)線性遞推式 公式法 解二階常系數(shù)線性遞推方程問題提出 有一類重要遞推式不能用前向和反向替換法求解 形如 概念解釋 1 二階 遞推式中未知項x n 和x n 2 在序列中相差兩個位置 2 常系數(shù) 遞推式中未知項系數(shù)為常數(shù) 3 線性 遞推式為未知項的線性組合 4 齊次 方程右端為0 即f n 0 5 非齊次 方程右端不為0 6 特征方程 齊次遞推方程的解 取決于和遞推式具有相同系數(shù)的一個二次方程即特征方程 定理1 設q1 q2是特征方程的兩個根 第一種情況 有兩個不相等實根 齊次遞推方程通解為 c1和c2為待定常數(shù) 37 遞推方程求解 二階常系數(shù)線性遞推式例1 第二種情況 有兩個相等實根 齊次遞推方程通解為 第三種情況 特征方程在實數(shù)域無解 略 定理2 把非齊次方程的特解和相應的齊次方程通解相加 得到該非齊次方程的通解 例1 求齊次遞推方程通解和特解解 該遞推方程的特征方程為 特征方程有兩個相等的實根 根據(jù)定理1 該遞推方程通解為 根據(jù)初始條件解出待定常數(shù) 得到一個特解 c1和c2為待定常數(shù) c1和c2為待定常數(shù) 38 遞推方程求解 二階常系數(shù)線性遞推式例2 例2 求非齊次遞推方程滿足初始條件的特解解 根據(jù)例1 該非齊次方程對應的齊次方程的通解為 注意 此時不能代入初始條件解出非齊次方程的一個特解 為什么 現(xiàn)在 求非齊次方程的一個特解 設特解為 由遞推式解得根據(jù)定理2 得到非齊次遞推方程的通解 疊加 據(jù)初始條件解出特解中待定常數(shù) 得特解 c1和c2為待定常數(shù) c1和c2為待定常數(shù) 39 遞推方程求解 k階常系數(shù)線性遞推式 公式法求解 k階常系數(shù)線性遞推式 二階的推廣 它的齊次遞推方程 方程右端項為0 即齊次方程的特征方程 相同系數(shù)的一個k次方程 超越方程 數(shù)值解法 40 遞推方程求解 k階常系數(shù)線性遞推式 2 求k階齊次遞推方程通解 定理1推廣 1 特征方程有k個不相等實根qk 齊次遞推方程通解為 2 特征方程有r個相等實根 重根 齊次遞推方程通解為 說明 k次特征方程有k個實根q1 q2 qk 其中有r個實根相同 這相同的r個實根為 ck為待定常數(shù) 41 遞推方程求解 k階常系數(shù)線性遞推式 3 求k階非齊次遞推方程特解 前面已求得其相應的齊次遞推方程通解 據(jù)定理2 再求得非齊次方程的任意一個特解 則兩者相加可得非齊次遞推方程通解 最后 根據(jù)給定初始條件可得滿足初始條件的非齊次遞推方程特解 對一般的非齊次遞推方程 不存在尋找特解的通用方法 只能用觀察法去假定特解的形式 然后用待定系數(shù)法確定系數(shù) 1 當f n 是n的t次多項式時 可設特解也是n的多項式即特解形式 2 當f n 是n的指數(shù)函數(shù) a b為待定常數(shù)時 設特解形式 1 b不是相應齊次方程的特征根時 2 b是相應齊次方程的e重特征根時 p為待定系數(shù) 42 遞推方程求解 k階常系數(shù)線性遞推式例 例 解遞歸方程解 1 求齊次遞推方程的特征根