《算法效率分析基礎(chǔ)》PPT課件.ppt

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