【文章內(nèi)容簡(jiǎn)介】 ?對(duì) 于 所 有 有 ：2 2 22 2 2 ( ) (( ) ( ( ) ) , )T n c g nT n O g n n n?? ?對(duì) 于 所 有 有 ：121 1 2 2123 1 2 1 21 1 2 23 1 3 2213312{ , } , { , } ,( ) ( )( ) ( ) [ ]{( ) ( )2 { ( ) , ( ) }( ) ( )( { ( ) ,( ) , ( ) } ( ) } )g n g nmc m a x c c n m a x n nc g n c g nc g n c g n ccm a xT n T nO m a xg n g n g n g na x g n g nc??????? ? ????取 且 則 ：21 利用極限比較增長(zhǎng)率 ?利用極限比較增長(zhǎng)率： 此法常用來(lái)比較兩個(gè)特定增長(zhǎng)函數(shù)的增長(zhǎng)率，簡(jiǎn)便。它根據(jù)極限定義， 對(duì)兩個(gè)函數(shù)的比值求極限，以判定哪個(gè)函數(shù)增長(zhǎng)更快。 : ( ) ( ( ) ) (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????????????????比 增 長(zhǎng) 慢與 增 長(zhǎng) 相 同比 增 長(zhǎng) 快不 存 在 : 該 法 不 適 用例 1：比較 (n1)和 n2的增長(zhǎng)率。（或證明 : (n1)∈ Θ(n2)） 22220 . 5 ( 1 ) 1 1 1 1li m li m li m ( 1 )2 2 21( 1 ) ( )2n n nn n n nn n nn n n? ? ? ? ? ???? ? ? ?? ? ? ?22 利用極限比較增長(zhǎng)率例 例 2： 2l o g nn比 較 和 的 增 長(zhǎng) 次 數(shù) 。2222l og ( l og ) 39。l i m l i m ( )( ) 39。1l ogl i m l i m 022l og1nnnnnnnenennnn? ? ? ?? ? ? ??? ? ?常 數(shù)羅 必 塔 法 則例 3： !2 nn比 較 和 的 增 長(zhǎng) 次 數(shù) 。2 ( )!lim lim ( )22lim 2 lim 2 ( )22nnnnnnnnnnnnnn ennee???? ? ? ?? ? ? ??? ? ? ?史 特 林 公 式23 漸進(jìn)效率的基本類(lèi)型 ?漸進(jìn)效率的基本類(lèi)型 類(lèi) 型 名 稱(chēng) 注 釋 1 常量 為數(shù)極少的效率最高的算法，難以舉出幾個(gè)例子。 通常，當(dāng)輸入規(guī)模變得無(wú)窮大的時(shí)候，算法的執(zhí)行 時(shí)間也會(huì)趨于無(wú)窮大。 logn 對(duì)數(shù) 算法每次循環(huán)都會(huì)消去問(wèn)題規(guī)模的一個(gè)常數(shù)因子。 n 線(xiàn)性 掃描規(guī)模為 n的列表（如順序查找）算法。 nlogn nlognn 諸多分治算法，包括合并排序和快速排序平均效率 屬于此類(lèi)型。 n2 二次 一般來(lái)說(shuō)，包含兩重嵌套循環(huán)的算法。 n 階方陣的 某些特定算法。 n3 三次 一般來(lái)說(shuō)，包含三重嵌套循環(huán)的算法。 2n 指數(shù) 求 n個(gè)元素集合的所有子集的算法?！爸笖?shù)”這個(gè) 術(shù)語(yǔ)常用在更廣泛的層面上，不僅包括這種類(lèi)型， 還包括那些增長(zhǎng)速度更快的算法如階乘。 n! 階乘 求 n個(gè)元素集合的完全排列的算法。 24 非遞歸算法分析 ★ 非遞歸算法的效率分析（很常用） 本節(jié)將系統(tǒng)地運(yùn)用前節(jié)的通用框架來(lái)分析非遞歸算法的效率。先從一個(gè) 簡(jiǎn)單的算法開(kāi)始，示范這類(lèi)算法分析的步驟。 例 1：從 n 個(gè)元素列表中查找最大值。 （用數(shù)組簡(jiǎn)單實(shí)現(xiàn)列表） 算法 MaxElement ( A[0...n1] ) // 求數(shù)組 A中元素的最大值 // 輸入：實(shí)數(shù)數(shù)組 A。 輸出： A中最大元素的值 maxval←A[0] for i←1 to n1 do if A[i] maxval // 每次循環(huán)時(shí)無(wú)條件執(zhí)行（必執(zhí)行） maxval←A[i] // 每次循環(huán)時(shí)有條件執(zhí)行（不一定執(zhí)行） return maxval 效率分析框架要求明確輸入規(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)率。 11( ) 1 ()1niC n n n??? ?????結(jié)論 ：本算法具有線(xiàn)性增長(zhǎng)率 26 復(fù)習(xí)：幾個(gè)常用求和公式 ?復(fù)習(xí)：幾個(gè)常用求和公式 12211111 2 1001()1 1 1 1 1111 2 ( 1 ) ( )22112111 ( 1 ) 。 2 2 11lg lgm m m m mi i i i i ii l i k i l i l i lmilmlnink k k k kinnni n i niinic a c a a b a bmli n n n n ni n nkaa a a a aai n n i? ? ? ? ????????????? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? ? ?? ? ? ? ???? ? ? ? ? ? ? ? ???? ? ? ? ???????2112 1 2 2 2 2 ( 1 ) 2 2ni n ninn??? ? ? ? ? ? ? ? ? ??27 例 2：元素唯一性問(wèn)題 例 2： 【 元素唯一性問(wèn)題 】 檢查給定數(shù)組的元素是否全部唯一 算法： UniqueElement ( A[0...n1] ) for i←0 to n2 do for j←i+1 to n1 do if A[ i ] = A[ j ] return false return true 輸入規(guī)模 ：數(shù)組元素個(gè)數(shù) n 基本操作 ：最內(nèi)層循環(huán)只有一個(gè)“比較”操作，選為基本操作。 效率種類(lèi) ：從循環(huán)結(jié)束條件可知，若比較的兩個(gè)元素相等，則提前結(jié)束 循環(huán)，返回“假”說(shuō)明數(shù)組元素不唯一。 最佳的情況是 ，首次比較就結(jié)束 循環(huán)，即數(shù)組開(kāi)始兩個(gè)元素就相同； 最差的情況是 ，循環(huán)結(jié)束前的最后 一次比較才發(fā)現(xiàn)相同的元素（最后兩個(gè)），或者該數(shù)組沒(méi)有相同元素， 都要完成全部循環(huán)次數(shù)，即比較次數(shù)就是循環(huán)次數(shù)。這里，我們研究其 最差效率 Cworst(n)。 0 1 2 2 1nn????? ??? ? ?i j 28 例 2：元素唯一性問(wèn)題 (續(xù) ) 外層 i 循環(huán)范圍： 0, n2 。 內(nèi)層 j 循環(huán)范圍： i+1, n1 建立增長(zhǎng) 函數(shù) （基本操作執(zhí)行次數(shù)與輸入規(guī)模 n 的求和表達(dá)式）： ? ?? ?2 2 20 0 0220202122120( ) ( 1 )( 1 ) ( 1 ) 1( 1 ) 1( 1 )221 1 11 1 ( 1 )1 ( 1 ) ( 1 ) 1( 2 ) ( 1 )2( ( 1 )21 ) ( )2(2)12n n nw orsti i inninjini iC n n innnnnninnn ninnnnnn??? ? ?? ? ??????? ?? ? ? ? ?? ? ? ? ?? ? ? ?????? ? ? ? ??? ? ? ? ????????? ? ?????20( 1 ) ( 1 ) ( 2 ) ( 3 ) 111 2 ( 1 ) ( 1 )2nin n n nninn??? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ??29 例 3： 【 矩陣乘法 】 時(shí)間效率分析 例 3：