【正文】 設(shè)各類輸入的概率分布，以推導(dǎo)出基本操作的平均次數(shù)。 但各類輸入的 概率模型 往往又難以驗證，雖然它可能很合理。 13 順序查找算法的平均時間效率 ? 順序查找算法的平均時間效率： 假設(shè)： (1) 成功查找的概率是 p (0≤p≤1)，查找不成功的概率是 1 p； (2) 對任意第 i 次查找，第一次成功匹配（查找成功）發(fā)生在列表第 i 個 位置的概率相同，即查找鍵位于列表任一位置上的概率相同 1/n ?；? 假設(shè)，在列表任一位置上查找成功的 概率為 p(1/n)（甚至可進(jìn)一步假設(shè) p=）。若查找成功的位置為 i ，算法做的比較次數(shù)（基本操作）為 i 次，考慮成功查找概率， 比較次數(shù)為 p(i/n)；若查找不成功，算法做的 比較次數(shù)為 n（列表全部查找一遍），考慮不成功查找概率，比較次數(shù) 則為 n(1p)。因此，算法平均效率： ()( 1 )( 1 2 ... ) ( 1 ) (12( ... ) ( 1 )1)2( 1 ) / 2 , 1( 1 )( 1 ),02av gCnp p n nn n p ninp p p p n pn n n npnnnppnnpnp???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?????? ?? ? ? ? ????統(tǒng) 計 平 均 14 攤銷效率 4 攤銷效率 它并不適合于算法的單次運行，而應(yīng)用于算法對同樣數(shù)據(jù)的多次運行。 我們知道，在有些情況下單次運行的時間代價可能比較昂貴，但 n 次 運行的 總時間花費明顯低于單次運行的最差效率乘以 n ，因此我們把 最差效率的高成本攤到各次運行中去，即攤銷效率。該做法與商業(yè)中 把固定資產(chǎn)成本按其使用年限攤銷到整個序列（各年）中的做法一致。 通常，具備這種運行特性的算法是在一定程度上的具有 “ 智能 ” 的算法， 通過 “ 學(xué)習(xí) ” 獲得 “ 知識 ” 累積，再運用知識庫中的有關(guān)知識對算法下次 如何執(zhí)行提供指導(dǎo)，從而提高以后運行的效率。一個例子：漢字拼音 輸入法中的動態(tài)詞頻調(diào)整算法。它統(tǒng)計不同用戶對某些字詞的使用率 （學(xué)習(xí)積累過程），來動態(tài)調(diào)整這些字詞下次出現(xiàn)的先后順序，高頻 先現(xiàn)，達(dá)到減少用戶翻閱時間的目的，提高了該算法的執(zhí)行效率。 后續(xù)章節(jié)中，除非專門說明，都將最差情況下時間耗費的極限作為算法 的時間耗費，稱時間復(fù)雜性或時間效率。求解過程稱為 時間漸進(jìn)分析 。 15 漸進(jìn)符號 ★ 漸進(jìn)符號和基本效率類型 上節(jié)指出，效率分析主要關(guān)心的是一個算法的 基本操作數(shù)隨問題規(guī)模的 增長率 （增長次數(shù)），即問題規(guī)模 n 變大情況下，該算法的基本操作數(shù) 增長的快慢（它是規(guī)模 n 的函數(shù) ——增長函數(shù)）。為了對增長函數(shù)作出 比較和歸類，通常使用三種符號： O,Ω,Θ(theta). 下面就這些符號先作一個非正式介紹（便于理解）。 T(n) 和 g(n) ：定義在自然數(shù)集合上的任意非負(fù)函數(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ù)集的上界。例如： 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 上界符號 Ω(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 和非負(fù)整數(shù) n0，使得下式成立： 3 2 3 2 4 2( ) , 0 . 0 0 0 0 1 ( ) , 1 ( )n n n n n n n? ? ? ? ? ? ? ?20 . 5 ( 1 ) ( )n n n? ? ?0 : ( ) ( )n n T n c g n??n0n()cg n()Tn規(guī)模 增長函數(shù) n0 之前情況無關(guān)緊要 上界 ( ) ( ( ) )T n O g n?最差效率分析 17 下界符號 證明： 證一： 據(jù)定義選?。? 證二： 據(jù)定義選?。? ?下屆符號 Ω 定義 ：把函數(shù) T(n)包含在 Ω(g(n))中， 記為 T(n)∈ Ω(g(n))；它成立的條件 是：對于足夠大的 n， T(n) 的下界 由 g(n)的常數(shù)倍決定。即存在正數(shù) c 和非負(fù)整數(shù) n0，使得下式成立： 21 0 0 5 ( )n O n??2( ) 1 0 0 5 1 0 0 ( 5 ) 1 0 1 1 0 1T n n n n n n n? ? ? ? ? ? ?當(dāng)220 ()101( ) ( ) , ( ),()5, g n nTncc g n T n O nn ?????證 畢2( ) 1 0 0 5 1 0 0 5 ( 1 ) 1 0 5 1 0 5T n n n n n n n? ? ? ? ? ? ?當(dāng)022( ) 1 0 0 5 , ( )105,( ) (1,) , ( ) ( )T n n g n nTnc g n T n O n? ? ?????證 畢n0n()cg n()Tn規(guī)模 增長函數(shù) n0 之前情況無關(guān)緊要 下界 ( ) ( ( ) )T n g n??最佳效率分析 0 : ( ) ( )n n T n c g n??18 同階符號 ?同階符號 Θ 定義 ：把函數(shù) T(n)包含在 Θ(g(n))中， 記為 T(n)∈ Θ(g(n))；它成立的條件 是：對于足夠大的 n， T(n) 的下界 和上界 均由 g(n)的常數(shù)倍決定。即 存在正數(shù) c 和非負(fù)整數(shù) n0，使得： 例：證明 證：注意到 上界情況： 下界情況： 0 1 2: ( ) ( ) ( )n n c g n T n c g n? ? ?n0n1 ()c g n()Tn規(guī)模 增長函數(shù) n0 之前情況無關(guān)緊要 ( ) ( ( ) )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 漸進(jìn)符號的有用性質(zhì) ?漸進(jìn)符號的有用性質(zhì)（ 3 證明從略） 性質(zhì) 1： 性質(zhì) 2： 性質(zhì) 3： 性質(zhì) 4： 性質(zhì) 4的價值 ：（證明見下頁） 某些算法是由兩個（以上）執(zhí)行部分組成，性質(zhì) 4指明：該算法的整體 效率由具有較大增長率的部分決定，即它效率最差的部分。舉例如下： 數(shù)組中特定元素的查找算法 ： 第一部分 ，用某種已知的排序算法對數(shù)組 排序，得到有序數(shù)組； 第二部分 ，對有序數(shù)組從頭至尾掃描，比較是否 與指定元素相等。若排序部分增長函數(shù)為 (n1)∈ O(n2)；第二部分的 增長函數(shù)為 n∈ O(n)，那么，算法的整體效率為 T(n) ∈ O(n2)。 ( ) ( ( ) ) , ( ) ( ( ) ) , ( ) ( ( ) )T n O g n g n O h n T n O h n? ? ?若 則 :( ) ( ( ) ) , 0 , ( ) ( ( ) )T n O K g n K T n O g n? ? ?若 則 :1 1 2 21 2 1 2( ) ( ( ) ) , ( ) ( ( ) )( ) ( ) ( ( ) ( ) )T n O g n T n O g nT n T n O g n g n???若則1 1 2 21 2 1 2( ) ( ( ) ) , ( ) ( ( ) )( ) ( ) ( { ( ) , ( ) } )T n O g n T n O g nT n T n O m a x g n g n????若則20 漸進(jìn)符號性質(zhì) 4的證明 性質(zhì) 4的證明 ： 1 1 2 21 2 1 2( ) ( ( ) ) , ( ) ( ( ) )( ) ( ) ( { ( ) , ( ) } )T n O g n T n O g nT n T n O m a x g n g n????若則1 1 11 1 1 ( ) (( ) ( ( ) ) , )T n c g nT n O g n n n??