【正文】 （秒、毫秒等）來度量算法的運(yùn)行時(shí)間呢？其 理由 如下： 1. 它依賴于特定計(jì)算機(jī)的運(yùn)行速度； 2. 它依賴于實(shí)現(xiàn)算法的代碼質(zhì)量；（程序員編程的水平問題） 3. 它依賴于編譯器的好壞；（編譯成機(jī)器碼的質(zhì)量，即指令條數(shù)） 4. 它還依賴于一些其他問題如操作系統(tǒng)的調(diào)度策略等。所以， 用基本操作執(zhí)行 次數(shù)來作為時(shí)間效率的度量 。 在定義了算法的輸入規(guī)模 n 和基本操作后，我們就可以建立起一個(gè)算法 ? 時(shí)間效率的分析框架 ： 對(duì)規(guī)模為 n 的算法，通過統(tǒng)計(jì)其基本操作的 執(zhí)行次數(shù)來度量算法的時(shí)間效率 。 n的一次、二次函數(shù)分別稱線性、二次增長率。函數(shù)值 T(n) 增加快慢，決定于這個(gè)增長函數(shù)特性； 也就是說，線性增長函數(shù)的函數(shù)值增加較慢，二次增長函數(shù)增加較快， 指數(shù)增長函數(shù)最快。 10 算法效率算例 ?算法的最優(yōu)、最差、平均效率 前述已知，我們用輸入規(guī)模 n 的函數(shù) T(n) 來度量算法的效率。下面以順序查找算法為例： 【 名稱 】 順序查找 【 要求 】 在列表中查找一次 給定項(xiàng) （查找鍵），該列表有 n 個(gè)元素。 最優(yōu)效率 3. 若查找鍵位于表尾（最末元素）或不存在，該算法將 比較 n 次。此時(shí)，相對(duì)于其他規(guī)模 為 n 的輸入，該算法運(yùn)行時(shí)間最長（最慢）。（ 最差效率分析的價(jià)值 ） 順序查找： Cworse(n) = n 2 最優(yōu)效率： 當(dāng)輸入規(guī)模為 n 時(shí)，算法在最優(yōu)情況下的效率。重要的是， 如果一個(gè)算法 的最優(yōu)效率都不能滿足實(shí)際需要，可立即拋棄該算法 。以后討論平均效率時(shí) 都引用其已知的推導(dǎo)結(jié)果。顯然，我們 不能通過求最優(yōu)和最差效率平均值的方法來求平均效率。 13 順序查找算法的平均時(shí)間效率 ? 順序查找算法的平均時(shí)間效率： 假設(shè)： (1) 成功查找的概率是 p (0≤p≤1)，查找不成功的概率是 1 p； (2) 對(duì)任意第 i 次查找，第一次成功匹配（查找成功）發(fā)生在列表第 i 個(gè) 位置的概率相同，即查找鍵位于列表任一位置上的概率相同 1/n 。 我們知道，在有些情況下單次運(yùn)行的時(shí)間代價(jià)可能比較昂貴，但 n 次 運(yùn)行的 總時(shí)間花費(fèi)明顯低于單次運(yùn)行的最差效率乘以 n ，因此我們把 最差效率的高成本攤到各次運(yùn)行中去，即攤銷效率。它統(tǒng)計(jì)不同用戶對(duì)某些字詞的使用率 （學(xué)習(xí)積累過程），來動(dòng)態(tài)調(diào)整這些字詞下次出現(xiàn)的先后順序，高頻 先現(xiàn)，達(dá)到減少用戶翻閱時(shí)間的目的，提高了該算法的執(zhí)行效率。為了對(duì)增長函數(shù)作出 比較和歸類，通常使用三種符號(hào)： O,Ω,Θ(theta). 下面就這些符號(hào)先作一個(gè)非正式介紹（便于理解）。例如： 2 2 2( ) , 1 0 0 5 ( ) , 0 . 5 ( 1 ) ( )n O n n O n n n O n? ? ? ? ?3 2 3 2 4 2( ) , 0 . 0 0 0 0 1 ( ) , 1 ( )n O n n O n n n O n? ? ? ? ?16 上界符號(hào) Ω(g(n)) ：增長次數(shù) 大于等于 g(n)（包括其常數(shù)倍， n 趨于無窮大）的 函數(shù)集合。例如： ?上界符號(hào) O （最常用） 定義 ：把函數(shù) T(n)包含在 O(g(n))中， 記為 T(n)∈ O(g(n))；它成立的條件 是：對(duì)于足夠大的 n， T(n) 的上界 由 g(n)的常數(shù)倍決定。舉例如下： 數(shù)組中特定元素的查找算法 ： 第一部分 ，用某種已知的排序算法對(duì)數(shù)組 排序，得到有序數(shù)組； 第二部分 ，對(duì)有序數(shù)組從頭至尾掃描，比較是否 與指定元素相等。 : ( ) ( ( ) ) (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的增長率。1l ogl i m l i m 022l og1nnnnnnnenennnn? ? ? ?? ? ? ??? ? ?常 數(shù)羅 必 塔 法 則例 3： !2 nn比 較 和 的 增 長 次 數(shù) 。 n 線性 掃描規(guī)模為 n的列表（如順序查找）算法。 n3 三次 一般來說，包含三重嵌套循環(huán)的算法。 24 非遞歸算法分析 ★ 非遞歸算法的效率分析（很常用） 本節(jié)將系統(tǒng)地運(yùn)用前節(jié)的通用框架來分析非遞歸算法的效率。 輸出： A中最大元素的值 maxval←A[0] for i←1 to n1 do if A[i] maxval // 每次循環(huán)時(shí)無條件執(zhí)行（必執(zhí)行） maxval←A[i] // 每次循環(huán)時(shí)有條件執(zhí)行（不一定執(zhí)行） return maxval 效率分析框架要求明確輸入規(guī)模和基本操作。 本算法每個(gè)數(shù)組元素都要進(jìn)行一次比較，故不區(qū)分最優(yōu)、最差和平均效率。 因此有： ?非遞歸算法效率分析的通用方案： 1 確定 輸入規(guī)模 ； 2 確定 基本操作 ；（一般情況：它總是位于算法的最內(nèi)層循環(huán)里） 3 考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關(guān)。 11( ) 1 ()1niC n n n??? ?????結(jié)論 ：本算法具有線性增長率 26 復(fù)習(xí)：幾個(gè)常用求和公式 ?復(fù)習(xí)：幾個(gè)常用求和公式 12211111 2 1001()1 1 1 1 1111 2 ( 1 ) ( )22112111 ( 1 ) 。這里，我們研究其 最差效率 Cworst(n)。本例均為 n1 30 例 3： 【 矩陣乘法 】 時(shí)間效率分析（續(xù)） 輸入規(guī)模 ：因是方陣，選擇矩陣的階 n 。但考慮操作的時(shí)間耗費(fèi)，對(duì)大多數(shù)計(jì)算機(jī)來講，乘法 比加法更費(fèi)時(shí)間，且算術(shù)運(yùn)算比賦值操作更費(fèi)時(shí)間。 建立增長 函數(shù) （基本操作數(shù)與輸入規(guī)模 n 的求和表達(dá)式） ： 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： 【 二進(jìn)制位數(shù) 】 一個(gè)十進(jìn)制正整數(shù)的二進(jìn)制位數(shù) 例 4： 【 二進(jìn)制位數(shù) 】 一個(gè)十進(jìn)制正整數(shù) n 的二進(jìn)制位數(shù) b。另外方法，本例循環(huán)次數(shù)為： 2l o gbn? ???? ???? 向 上 取 整 ， 不 小 于 該 實(shí) 數(shù) 的 整 數(shù)/2n????2 b m axn?22l o g l (lo o g )gb nnn? ???????一點(diǎn)說明 ：考慮對(duì)數(shù)換底公式 l o g l o gl o g aab bnn?常 數(shù)因此，當(dāng)我們分析增長率時(shí)，忽略對(duì)數(shù) 的底，簡單寫成 logn 32 遞歸算法效率分析 ★ 遞歸算法效率分析 ? 序列和遞推關(guān)系 ? 定義 ：數(shù)字序列是數(shù)字的一個(gè)有序列表。 ? 序列的兩種定義法 ： 1. 通項(xiàng)定義法：例如正偶數(shù)序列 2. 方程定義法：把序列的 通項(xiàng) 和 其他項(xiàng) 用方程定義，并規(guī)定序列的首項(xiàng) 或前幾項(xiàng)的值，例如： 0n?(1) 4x ?( ) 2 ( 1 ) , 0x n n n? ? ?( ) ( 1 ) , 1( 0 ) 0x n x n n nx? ? ? ??← 遞推方程或遞推關(guān)系，簡稱遞推式 ← 初始條件 33 解遞推方程的概念 ? 解遞推方程的概念 解遞推方程，意味著找到序列 通項(xiàng) ，既滿足遞推式又滿足初始條件。一個(gè)特定序列由初始條件（初值）確定。例子如下： 遞推式： 根據(jù)初始條件和遞推式，生成序列前幾項(xiàng)： ( ) 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?? ? ?? ? ?? ? ? ??右 端左 端驗(yàn)證： 代入法 方法評(píng)價(jià)：有時(shí)候很難從序列前幾項(xiàng)中找到通項(xiàng)！ 漢諾 (hanoi)塔游戲 35 遞推方程求解：反向替換法 ? 反向替換法 ：（很有效）遞推方向： 前 ← 后 用遞推式將 x(n) 逐次表示為 x(n1), x(n2), x(n3), ..., x(nk), k=1, 2, 3, ... 然后通過運(yùn)算化簡，得序列通項(xiàng)（解）。 2. 常系數(shù)： 遞推式中未知項(xiàng)系數(shù)為常數(shù)。 6. 特征方程：齊次遞推方程的解，取決于和遞推式具有相同系數(shù)的一個(gè)