第2章_算法分析基礎(chǔ)

1、海南大學(xué)信息科學(xué)技術(shù)學(xué)院College of Information Science and Technology, Hainan University2022-6-27Algorithm Introduction2n算法分析（算法分析（Algorithm Analysis）n算法復(fù)雜性算法復(fù)雜性（Algorithm Complexity ）算法復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需計(jì)算機(jī)資源的多少算法復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需計(jì)算機(jī)資源的多少.計(jì)算機(jī)中最重要的兩種資源是計(jì)算機(jī)中最重要的兩種資源是時(shí)間時(shí)間和和空間資源。更確切地說，空間資源。更確切地說，算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的

2、算法的復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量量，需要的，需要的時(shí)間資源的量稱為時(shí)間復(fù)雜性；需要的空間資源的量稱為空時(shí)間資源的量稱為時(shí)間復(fù)雜性；需要的空間資源的量稱為空間復(fù)雜性，如下：間復(fù)雜性，如下：n 時(shí)間復(fù)雜性（時(shí)間復(fù)雜性（Time Complexity）n 空間復(fù)雜性（空間復(fù)雜性（Space Complexity）2.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析2022-6-27Algorithm Introduction3n算法時(shí)間復(fù)雜性分析算法時(shí)間復(fù)雜性分析這是一種這是一種事前事前分析估算的方法，對(duì)算法所消耗資源的一種漸分析估算的方法，對(duì)算法所消耗資源的一種漸進(jìn)分析方法。進(jìn)分析方法。漸

3、進(jìn)分析：忽略具體機(jī)器、編程語言和編譯器的影響，只關(guān)漸進(jìn)分析：忽略具體機(jī)器、編程語言和編譯器的影響，只關(guān)注在輸入規(guī)模增大時(shí)算法運(yùn)行時(shí)間的注在輸入規(guī)模增大時(shí)算法運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)增長(zhǎng)趨勢(shì)。這大大降低。這大大降低了算法分析的難度，從了算法分析的難度，從數(shù)量級(jí)數(shù)量級(jí)的角度評(píng)價(jià)算法的效率。的角度評(píng)價(jià)算法的效率。 C=F（N,I,A） TT（N）N為問題規(guī)模，為問題規(guī)模，I為算法輸入，為算法輸入，A為算法本身為算法本身2.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析2022-6-27Algorithm Introduction4n輸入規(guī)模與基礎(chǔ)語句輸入規(guī)模與基礎(chǔ)語句精確地表示算法的運(yùn)行時(shí)間函數(shù)精確地表示算

4、法的運(yùn)行時(shí)間函數(shù)T（N）常常是很困難的，）常常是很困難的，考慮到算法分析的主要目的在于比較求解同一個(gè)問題的不同考慮到算法分析的主要目的在于比較求解同一個(gè)問題的不同算法效率，為精簡(jiǎn)客觀地反映一個(gè)算法的運(yùn)行時(shí)間，用算法算法效率，為精簡(jiǎn)客觀地反映一個(gè)算法的運(yùn)行時(shí)間，用算法中中基本語句的執(zhí)行次數(shù)基本語句的執(zhí)行次數(shù)來度量算法的工作量。來度量算法的工作量?；菊Z句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)基本語句：執(zhí)行次數(shù)與整個(gè)算法的執(zhí)行次數(shù)正比正比的語句，對(duì)的語句，對(duì) 算法運(yùn)行時(shí)間算法運(yùn)行時(shí)間貢獻(xiàn)最大貢獻(xiàn)最大，是算法中，是算法中最重要最重要的操作。的操作。2.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析例2.1 對(duì)

5、如下順序查找算法，請(qǐng)找出輸入規(guī)模和基本語句 int SeqSearch(int A, int n, int k)for(int i=0; in; i+)if(Ai=k) break;if(i=n) return 0;else return (i+1);2022-6-27Algorithm Introduction52.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析例2.2 對(duì)如下起泡排序算法，請(qǐng)找出輸入規(guī)模和基本語句 void SubbleSort(int r, int n)int bound,exchange=n-1;while(exchange!=0)/當(dāng)上一趟排序有記錄交換時(shí)當(dāng)上一趟排序有

6、記錄交換時(shí)bound=exchange;exchange=0;for(int j=0; jrj+1) int temp=rj; rj=rj+1; rj+1=temp; exchange=j/記載每一次記錄交換的位置記載每一次記錄交換的位置2022-6-27Algorithm Introduction62.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析例2.3 下列算法實(shí)現(xiàn)將兩個(gè)升序序列合并成一個(gè)升序序列，請(qǐng)找出輸入規(guī)模和基本語句 void Union(int A, int n, int B, int m, int C)int i=0,j=0,k=0;while(in & jm)if(Ai

7、=Bj) Ck+=Ai+; /Ai和和Bj較小者存入較小者存入Ckelse Ck+=Bj+;while( in) Ck+=Ai+;while( jm) Ck+=Bj+;2022-6-27Algorithm Introduction72.1 算法的時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性分析 定義定義2.1 若存在兩個(gè)正常數(shù)若存在兩個(gè)正常數(shù)c和和n 0 ，對(duì)于任意，對(duì)于任意nn 0，都有，都有T(n)cf(n)，就稱函數(shù)，就稱函數(shù)T(n)O(f(n) 。 2022-6-27Algorithm Introduction82.1.2 算法的漸進(jìn)分析算法的漸進(jìn)分析算法的漸進(jìn)分析并不是度量算法的時(shí)間量，而是度量算

8、法運(yùn)行算法的漸進(jìn)分析并不是度量算法的時(shí)間量，而是度量算法運(yùn)行時(shí)間的時(shí)間的增長(zhǎng)趨勢(shì)增長(zhǎng)趨勢(shì)。只考察當(dāng)輸入規(guī)模充分大時(shí)，算法中基本語。只考察當(dāng)輸入規(guī)模充分大時(shí)，算法中基本語句的執(zhí)行次數(shù)的漸近意義下的階，常用大（讀歐）句的執(zhí)行次數(shù)的漸近意義下的階，常用大（讀歐）O表示。表示。上界（增長(zhǎng)率的上限），用上界（增長(zhǎng)率的上限），用O表示表示大大O符號(hào)描述增長(zhǎng)率的上限，表示符號(hào)描述增長(zhǎng)率的上限，表示T(n)的增長(zhǎng)最多像的增長(zhǎng)最多像f(n)增增長(zhǎng)的那樣快。長(zhǎng)的那樣快。cf(n)T(n)nono之前的情況不重要執(zhí)行次數(shù)問題規(guī)模例例2.4. 分析例分析例2.3中合并算法的時(shí)間復(fù)雜性中合并算法的時(shí)間復(fù)雜性解：解：1、

9、假設(shè)退出第、假設(shè)退出第1個(gè)循環(huán)后個(gè)循環(huán)后in, j=m，說明序列，說明序列A處理完畢，處理完畢，第第2個(gè)循環(huán)將不執(zhí)行，第個(gè)循環(huán)將不執(zhí)行，第3個(gè)循環(huán)執(zhí)行。算法的時(shí)間復(fù)雜性為：個(gè)循環(huán)執(zhí)行。算法的時(shí)間復(fù)雜性為：O(n+m+m-m)=O(n+m)2、 假設(shè)退出第假設(shè)退出第1個(gè)循環(huán)后個(gè)循環(huán)后in, j=m，說明序列，說明序列B處理完畢，處理完畢，第第2個(gè)循環(huán)將執(zhí)行，第個(gè)循環(huán)將執(zhí)行，第3個(gè)循環(huán)不執(zhí)行。算法的時(shí)間復(fù)雜性為：個(gè)循環(huán)不執(zhí)行。算法的時(shí)間復(fù)雜性為：O(n+m+n-n)=O(n+m)綜上，算法的時(shí)間復(fù)雜性為綜上，算法的時(shí)間復(fù)雜性為O(n+m)2022-6-27Algorithm Introductio

10、n92.1.2 算法的漸進(jìn)分析算法的漸進(jìn)分析有些算法的時(shí)間代價(jià)只依賴于問題的輸入規(guī)模，而與輸入的具體數(shù)據(jù)無關(guān)。如上例合并算法。但有些算法，即使輸入規(guī)模相同，如果輸入數(shù)據(jù)不同，其時(shí)間代價(jià)也不相同。2022-6-27Algorithm Introduction102.1.3 2.1.3 最好、最壞和平均情況最好、最壞和平均情況 2022-6-27Algorithm Introduction11例例2.52.5： 在一維整型數(shù)組在一維整型數(shù)組A n 中中順序查找順序查找與給定值與給定值k相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為相等的元素（假設(shè)該數(shù)組中有且僅有一個(gè)元素值為k） int Find (

11、int A , int n) for (i=0; irj+1最好情況：記錄已經(jīng)是升序排列，算法只執(zhí)行一次，比較n-1次，時(shí)間復(fù)雜性為O(n)最壞情況：記錄是降序排列，每趟只是無序序列中最大的記錄交換到最終位置，所以算法執(zhí)行n-1趟，第i趟比較n-i次比較，則記錄的比較次數(shù)為 ，時(shí)間復(fù)雜性O(shè)(n2)平均情況：O(n2)，過程略11(1)()2nin nni2.1.5 遞歸算法的時(shí)間復(fù)雜性分析遞歸算法的時(shí)間復(fù)雜性分析 1. 猜測(cè)技術(shù)猜測(cè)技術(shù):對(duì)對(duì)遞推關(guān)系式遞推關(guān)系式估計(jì)估計(jì)一個(gè)一個(gè)上限上限，然后（用數(shù)學(xué)歸納法）證明它正確。如然后（用數(shù)學(xué)歸納法）證明它正確。如果成功，試著果成功，試著收縮上限收縮上限

12、。如果失敗，放。如果失敗，放松限制再試著證明。直到上限符合要求。松限制再試著證明。直到上限符合要求。v 遞歸算法是分而治之的方法。遞歸算法是分而治之的方法。v 遞歸算法時(shí)間復(fù)雜性分析的關(guān)鍵：根據(jù)遞遞歸算法時(shí)間復(fù)雜性分析的關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)系式，然后求解這個(gè)遞歸過程建立遞推關(guān)系式，然后求解這個(gè)遞推關(guān)系式。推關(guān)系式。2. 猜測(cè)技術(shù)猜測(cè)技術(shù) + + 2)2(221)(nnnTnnT補(bǔ)例補(bǔ)例1 使用猜測(cè)技術(shù)分析二路使用猜測(cè)技術(shù)分析二路歸并排序算法的時(shí)間復(fù)雜性。歸并排序算法的時(shí)間復(fù)雜性。二路歸并排序運(yùn)行時(shí)間遞推式：二路歸并排序運(yùn)行時(shí)間遞推式：假定假定T(n)n2，需證明這個(gè)猜測(cè)是正確的。為方便

13、假定，需證明這個(gè)猜測(cè)是正確的。為方便假定n=2kT(2)=122成立，對(duì)所有成立，對(duì)所有in，假設(shè)，假設(shè)T(i)i2，則：，則：T(2n)2T(n)+2n2n2+2n 4n2=(2n)2故得，故得，T(n)=O(n2)成立成立2. 猜測(cè)技術(shù)猜測(cè)技術(shù) O(n2)是最小上限？如果猜測(cè)更小一些，如是最小上限？如果猜測(cè)更小一些，如T(n)cn，證明失敗。，證明失敗。即說明上限即說明上限 應(yīng)在應(yīng)在n和和n2之間。之間。再試試再試試T(n)nlognT(2)=1 2log2成立，對(duì)所有成立，對(duì)所有in，假設(shè)，假設(shè)T(i) ilogi ，則：，則：T(2n)2T(n)+2n2nlogn +2n=2n(log

14、n+1) =2nlog(2n)故得，故得，T(n)=O(nlogn)成立成立2. 擴(kuò)展遞歸技術(shù)擴(kuò)展遞歸技術(shù) + + 15)2(217)(2nnnTnnT)(10310)212(57257)(22212102nOnnnnnnnnTkkii + + + + 222112222225)2(52)2(52) 1 (25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+ + + + + + + + + + + + + + LL例2.7 使用擴(kuò)展遞歸技術(shù)分析下面遞推式的時(shí)間復(fù)雜性為方便假定n=2k。將遞推式進(jìn)行擴(kuò)展3. 通用分治遞推式通用分治遞

15、推式大小為大小為n的原問題分成若干個(gè)大小為的原問題分成若干個(gè)大小為n/b的子問題，的子問題，其中其中a個(gè)子問題需要求解，而個(gè)子問題需要求解，而cnk是合并各個(gè)子問題是合并各個(gè)子問題的解需要的工作量。的解需要的工作量。 + + 1)(1)(ncnbnaTncnTk kkkbkkabanObannObanOnTb)()log()()(log定理定理2.1 設(shè)設(shè)T(n)是一個(gè)非遞減函數(shù)，且滿足通用分治遞推式，是一個(gè)非遞減函數(shù)，且滿足通用分治遞推式，則有如下結(jié)果成立。則有如下結(jié)果成立。 3. 通用分治遞推式通用分治遞推式證明：用擴(kuò)展遞歸技術(shù)對(duì)通用分治遞推式進(jìn)行推導(dǎo)，假定a=bm211000( )( )

16、()( ) )(1)().( )()()ikkkmmkkkmkmmmm ikm i ikmm iiiinnnT naTcna aTccnbbbnna Tacaccnbbnbcaca bcaab+ +求和是個(gè)幾何級(jí)數(shù)，比率r=bk/a，且,有以下三種情況：loglogbbnamaan3. 通用分治遞推式通用分治遞推式loglog0logk0101(1)1:,a,( )()1(2)1:1 log n 1,an ,( )(log n)1(3)1:(r )T(n) O(a)()( )1bbbmaaimimaimkbbimmimmmkmkirrnT nOnrrrmnT nOnrrrOrObOnr+由于所

17、以由于所以，所以，2.2 算法的空間復(fù)雜性分析算法的空間復(fù)雜性分析算法在運(yùn)行過程中所需的存儲(chǔ)空間包括：算法在運(yùn)行過程中所需的存儲(chǔ)空間包括：（1）輸入輸出數(shù)據(jù)占用的空間。取決于問題，與算法無關(guān)）輸入輸出數(shù)據(jù)占用的空間。取決于問題，與算法無關(guān)（2）算法本身占用的空間。大小固定）算法本身占用的空間。大小固定（3）執(zhí)行算法需要的輔助空間。正是空間復(fù)雜性所指）執(zhí)行算法需要的輔助空間。正是空間復(fù)雜性所指S(n)=O(f(n)算法輸入輸出數(shù)據(jù)輔助空間2.2 算法的空間復(fù)雜性分析算法的空間復(fù)雜性分析例例2.8 分析例分析例2.2中起泡排序算法的空間復(fù)雜性。中起泡排序算法的空間復(fù)雜性。解：輸入輸出都在解：輸入輸

18、出都在rn中，聲明了中，聲明了3個(gè)簡(jiǎn)單變量：個(gè)簡(jiǎn)單變量：exchange、bound和和temp。所以空間復(fù)雜性為。所以空間復(fù)雜性為O(1)如果算法所需的輔助空間相對(duì)于問題的輸入規(guī)模來說是一個(gè)常如果算法所需的輔助空間相對(duì)于問題的輸入規(guī)模來說是一個(gè)常數(shù)，我們稱此算法為原地（或就地）工作。起泡排序算法屬于數(shù)，我們稱此算法為原地（或就地）工作。起泡排序算法屬于就地性質(zhì)。就地性質(zhì)。例例2.9 分析例分析例2.3中合并算法的空間復(fù)雜性。中合并算法的空間復(fù)雜性。解：合并不能就地進(jìn)行，需要將合并結(jié)果存入另外一個(gè)數(shù)組中。解：合并不能就地進(jìn)行，需要將合并結(jié)果存入另外一個(gè)數(shù)組中。設(shè)序列設(shè)序列A的長(zhǎng)度為的長(zhǎng)度為n，

19、序列，序列B的長(zhǎng)度為的長(zhǎng)度為m，則合并后的有序序列，則合并后的有序序列的長(zhǎng)度為的長(zhǎng)度為n+m，因此算法的空間復(fù)雜性為，因此算法的空間復(fù)雜性為O(n+m)2.3 最優(yōu)算法最優(yōu)算法同一個(gè)問題可能會(huì)存在多種算法，是否有求同一個(gè)問題可能會(huì)存在多種算法，是否有求解該問題的最優(yōu)算法？解該問題的最優(yōu)算法？如果能夠知道一個(gè)問題的計(jì)算復(fù)雜性如果能夠知道一個(gè)問題的計(jì)算復(fù)雜性下界下界，也就是求解該問題的任何算法（包括尚未發(fā)現(xiàn)的也就是求解該問題的任何算法（包括尚未發(fā)現(xiàn)的算法）所需的時(shí)間下界，就可以較準(zhǔn)確地評(píng)價(jià)各算法）所需的時(shí)間下界，就可以較準(zhǔn)確地評(píng)價(jià)各種算法的效率，確定算法還有多少改進(jìn)余地。種算法的效率，確定算法還有

20、多少改進(jìn)余地。2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界下界下界是指求解問題所需的是指求解問題所需的最少最少工作量。通常工作量。通常采用大采用大（讀歐米伽）表示。例如，已經(jīng)證明基于（讀歐米伽）表示。例如，已經(jīng)證明基于比較的排序算法的時(shí)間下界是比較的排序算法的時(shí)間下界是(nlog2n)，意味著，意味著不存在時(shí)間復(fù)雜性小于不存在時(shí)間復(fù)雜性小于O(nlog2n)的基于比較的排的基于比較的排序算法。序算法。 定義定義2.2 若存在兩個(gè)正常數(shù)若存在兩個(gè)正常數(shù)c和和n 0 ，對(duì)于任意，對(duì)于任意nn 0，都有，都有T(n)cg(n)，就稱，就稱T(n) (g(n) 。 2022-6-27Algor

21、ithm Introduction27大大符號(hào)描述增長(zhǎng)率的下限，表示符號(hào)描述增長(zhǎng)率的下限，表示T(n)的增長(zhǎng)至少像的增長(zhǎng)至少像g(n)增增長(zhǎng)的那樣快。長(zhǎng)的那樣快。如果能找到一個(gè)盡可能大的函數(shù)如果能找到一個(gè)盡可能大的函數(shù)g(n)使得求解該問題的所有使得求解該問題的所有算法都可以在算法都可以在(g(n)時(shí)間內(nèi)完成，則稱時(shí)間內(nèi)完成，則稱g(n)為該問題的計(jì)算為該問題的計(jì)算復(fù)雜性下界。復(fù)雜性下界。cg(n)T(n)nono之前的情況不重要執(zhí)行次數(shù)問題規(guī)模2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界 定義定義2.3 若存在三個(gè)正常數(shù)若存在三個(gè)正常數(shù)c1、c2和和n 0 ，對(duì)于任意，對(duì)于任意nn

22、0，都有都有c1 f(n) T(n) c2 f(n)，就稱，就稱T(n) (f(n) 。 2022-6-27Algorithm Introduction28符號(hào)意味著符號(hào)意味著T(n)與與f(n)同階，用來表示算法的精確階。同階，用來表示算法的精確階。問題的計(jì)算復(fù)雜性上下界（準(zhǔn)確界）問題的計(jì)算復(fù)雜性上下界（準(zhǔn)確界）n0問題規(guī)模問題規(guī)模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前之前的情況的情況無關(guān)緊無關(guān)緊要要T( (n) )c2f( (n) )c1f( (n) )2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界例：例：T(n)=3n-1，上界？下界？上下界？，上界？下界？上下界？解：解：當(dāng)當(dāng)n1時(shí)，時(shí)，3n

23、-13n=(n)當(dāng)當(dāng)n1時(shí)，時(shí)，3n-1 3n-n=2n=(n)當(dāng)當(dāng)n1時(shí)，時(shí)， 3n 3n-1 2n，則，則3n-1=(n)2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界大大常與大常與大O配合以證明某問題的一個(gè)特定算配合以證明某問題的一個(gè)特定算法是該問題的最優(yōu)算法，或是該問題中的某算法法是該問題的最優(yōu)算法，或是該問題中的某算法類中的最優(yōu)算法。一般情況下，如果能證明某問類中的最優(yōu)算法。一般情況下，如果能證明某問題的時(shí)間下界是題的時(shí)間下界是(g(n)，那么，對(duì)以時(shí)間，那么，對(duì)以時(shí)間O(g(n)來求解該問題的任何算法（其實(shí)就是確定算法的來求解該問題的任何算法（其實(shí)就是確定算法的精確階是精確階

24、是 (g(n)），都認(rèn)為是求解該問題的最），都認(rèn)為是求解該問題的最優(yōu)算法。優(yōu)算法。2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界例例2.10 如下算法實(shí)現(xiàn)在一個(gè)數(shù)組中求最小值元素，如下算法實(shí)現(xiàn)在一個(gè)數(shù)組中求最小值元素，證明該算法是最優(yōu)算法。證明該算法是最優(yōu)算法。int ArrayMin(int a, int n)int min=a0;for(int i=1;in;i+) if(aimin) min=ai;return min;2.3.1 問題的計(jì)算復(fù)雜性下界問題的計(jì)算復(fù)雜性下界證明：算法需要進(jìn)行n-1次比較，時(shí)間復(fù)雜性是O(n)。下面要證明問題的下界是(n)，即對(duì)于任何n個(gè)整數(shù)，求最小值

25、元素至少需要進(jìn)行n-1次比較。將n個(gè)整數(shù)分為三個(gè)動(dòng)態(tài)的集合：A（待比較數(shù)集合），B（非最小數(shù)集合），C（最小數(shù)集合）。任何一個(gè)通過比較求最小值元素的算法都要從(n,0,0)狀態(tài)開始，最終到達(dá)(0,n-1,1)。這個(gè)過程實(shí)際上是將元素從A向B和C移動(dòng)，但每次比較，至多能把一個(gè)較大元素從集合A移向集合B，因此，任何求最小值算法至少要進(jìn)行n-1次比較，其時(shí)間下界是(n)。所以算法是最優(yōu)算法。初始狀態(tài)(n,0,0)完成狀態(tài)(0,n-1,1)算法運(yùn)行確定和證明某個(gè)問題的計(jì)算復(fù)雜性下界是很困難的，因?yàn)椴豢赡苊杜e該問題的所有算法。事實(shí)中，存在大量問題，它們的下界是不清楚的。2.3.2 平凡下界平凡下界平凡下

26、界：使用平凡下界：使用計(jì)數(shù)計(jì)數(shù)方法得出的算法復(fù)雜性下界。即方法得出的算法復(fù)雜性下界。即對(duì)問題的輸入中必須要處理的元素進(jìn)行計(jì)數(shù)，同時(shí)對(duì)必須對(duì)問題的輸入中必須要處理的元素進(jìn)行計(jì)數(shù)，同時(shí)對(duì)必須要輸出的元素進(jìn)行計(jì)數(shù)，得到一個(gè)平凡下界。要輸出的元素進(jìn)行計(jì)數(shù)，得到一個(gè)平凡下界。例如，任何生成例如，任何生成n個(gè)不同元素的所有排列對(duì)象的算法個(gè)不同元素的所有排列對(duì)象的算法必定屬于必定屬于(n!)，因?yàn)檩敵龅囊?guī)模就是，因?yàn)檩敵龅囊?guī)模就是n！平凡下界很容易得出，但往往過小而失去意義。例如，平凡下界很容易得出，但往往過小而失去意義。例如，TSP問題的平凡下界是問題的平凡下界是(n2)（輸入是（輸入是n(n-1)/2個(gè)

27、城市間的個(gè)城市間的距離），但沒有意義，至今沒有找到一個(gè)多項(xiàng)式時(shí)間算法。距離），但沒有意義，至今沒有找到一個(gè)多項(xiàng)式時(shí)間算法。2.3.3 判定樹模型判定樹模型許多算法的工作方式都是對(duì)輸入元素進(jìn)行許多算法的工作方式都是對(duì)輸入元素進(jìn)行比較比較，例如排序，例如排序和查找算法，故可以用和查找算法，故可以用判定樹判定樹來研究這些算法的時(shí)間性能。來研究這些算法的時(shí)間性能。判定樹：滿足如下條件的二叉樹：判定樹：滿足如下條件的二叉樹：（1）每個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)形如）每個(gè)內(nèi)部結(jié)點(diǎn)對(duì)應(yīng)形如xy的比較，根據(jù)關(guān)系成立與的比較，根據(jù)關(guān)系成立與否，控制轉(zhuǎn)移到左右子樹；否，控制轉(zhuǎn)移到左右子樹；（2）每個(gè)葉子結(jié)點(diǎn)表示問題的一個(gè)結(jié)果。

28、從根到葉子結(jié)點(diǎn)）每個(gè)葉子結(jié)點(diǎn)表示問題的一個(gè)結(jié)果。從根到葉子結(jié)點(diǎn)所走過的路徑代表算法執(zhí)行的過程，路徑的長(zhǎng)度即代表算所走過的路徑代表算法執(zhí)行的過程，路徑的長(zhǎng)度即代表算法執(zhí)行的時(shí)間法執(zhí)行的時(shí)間2.3.3 判定樹模型判定樹模型例例2.11 用判定樹模型求解排序問題的時(shí)間下界。用判定樹模型求解排序問題的時(shí)間下界。解：根據(jù)排序算法中的比較，建立起判定樹來描述算法，解：根據(jù)排序算法中的比較，建立起判定樹來描述算法，則則判定樹的高度就是算法的下界判定樹的高度就是算法的下界。補(bǔ)充材料：補(bǔ)充材料：算法的實(shí)驗(yàn)分析算法的實(shí)驗(yàn)分析 漸進(jìn)分析能夠在數(shù)量級(jí)上對(duì)算法進(jìn)行精確度量，但數(shù)漸進(jìn)分析能夠在數(shù)量級(jí)上對(duì)算法進(jìn)行精確度量，

29、但數(shù)學(xué)不是萬能的，許多貌似簡(jiǎn)單的算法很難用數(shù)學(xué)的精學(xué)不是萬能的，許多貌似簡(jiǎn)單的算法很難用數(shù)學(xué)的精確性和嚴(yán)格性來分析，尤其在做確性和嚴(yán)格性來分析，尤其在做平均效率平均效率分析時(shí)。分析時(shí)。 算法的算法的實(shí)驗(yàn)分析實(shí)驗(yàn)分析是一種事后計(jì)算的方法，通常需要將是一種事后計(jì)算的方法，通常需要將算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。例如可在程序中算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。例如可在程序中設(shè)置計(jì)數(shù)器變量來記錄基本語句的執(zhí)行次數(shù)設(shè)置計(jì)數(shù)器變量來記錄基本語句的執(zhí)行次數(shù)。void SubbleSort(int r, int n)int count1,count2=0;int bound,exchange=n-1;whil

30、e(exchange!=0)/當(dāng)上一趟排序有記錄交換時(shí)當(dāng)上一趟排序有記錄交換時(shí)bound=exchange;exchange=0;for(int j=0; jrj+1) int temp=rj; rj=rj+1; rj+1=temp; count2+=3; exchange=j;/記載每一次記錄交換的位置記載每一次記錄交換的位置cout“比較次數(shù)是比較次數(shù)是”count1endl;cout“移動(dòng)次數(shù)是移動(dòng)次數(shù)是”count2endl;2022-6-27Algorithm Introduction37補(bǔ)充材料補(bǔ)充材料 算法的實(shí)驗(yàn)分析算法的實(shí)驗(yàn)分析 一般步驟：一般步驟：1. 明確實(shí)驗(yàn)?zāi)康拿鞔_實(shí)驗(yàn)?zāi)康?（驗(yàn)