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

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

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

4、慮到算精確地表示算法的運行時間函數(shù)常常是很困難的，考慮到算法分析的主要目的在于比較求解同一個問題的不同算法效率，法分析的主要目的在于比較求解同一個問題的不同算法效率，為精簡客觀地反映一個算法的運行時間，用算法中為精簡客觀地反映一個算法的運行時間，用算法中基本語句基本語句的執(zhí)行次數(shù)來度量算法的工作量。的執(zhí)行次數(shù)來度量算法的工作量?；菊Z句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)正比的語句，對基本語句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)正比的語句，對 算法運行時間貢獻最大，是算法中最重要的操作。算法運行時間貢獻最大，是算法中最重要的操作。2.1 算法的時間復(fù)雜性分析算法的時間復(fù)雜性分析例2.1 對如下順序查找算法

5、，請找出輸入規(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-2Algorithm Introduction52.1 算法的時間復(fù)雜性分析算法的時間復(fù)雜性分析例2.2 對如下起泡排序算法，請找出輸入規(guī)模和基本語句 void SubbleSort(int r, int n)int bound,exchange=n-1;while(exchange!=0)/當(dāng)上一趟排序有記錄交換時當(dāng)上一趟排序有記錄交換時boun

6、d=exchange;exchange=0;for(int j=0; jrj+1) int temp=rj; rj=rj+1; rj+1=temp; exchange=j/記載每一次記錄交換的位置記載每一次記錄交換的位置2022-6-2Algorithm Introduction62.1 算法的時間復(fù)雜性分析算法的時間復(fù)雜性分析例2.3 下列算法實現(xiàn)將兩個升序序列合并成一個升序序列，請找出輸入規(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=Bj) Ck+=A

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

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

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

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

11、0; irj+1最好情況：記錄已經(jīng)是升序排列，算法只執(zhí)行一次，比較n-1次，時間復(fù)雜性為O(n)最壞情況：記錄是降序排列，每趟只是無序序列中最大的記錄交換到最終位置，所以算法執(zhí)行n-1趟，第i趟比較n-i次比較，則記錄的比較次數(shù)為 ，時間復(fù)雜性O(shè)(n2)平均情況：O(n2)，過程略2.1.4 2.1.4 非遞歸算法的時間復(fù)雜性分析非遞歸算法的時間復(fù)雜性分析 11(1)()2nin nni2022-6-2Algorithm Introduction15n非遞歸算法分析的一般步驟非遞歸算法分析的一般步驟 1. 決定用哪個（或哪些）參數(shù)作為算法問題規(guī)模的度量決定用哪個（或哪些）參數(shù)作為算法問題規(guī)模的

12、度量2. 找出算法中的基本語句找出算法中的基本語句3. 檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模4. 建立基本語句執(zhí)行次數(shù)的求和表達式建立基本語句執(zhí)行次數(shù)的求和表達式5. 用漸進符號表示這個求和表達式用漸進符號表示這個求和表達式關(guān)鍵：建立一個代表算法運行時間的關(guān)鍵：建立一個代表算法運行時間的求和表達式求和表達式，然后，然后用漸進符號表示用漸進符號表示這個求和表達式這個求和表達式。 2.1.4 2.1.4 非遞歸算法的時間復(fù)雜性分析非遞歸算法的時間復(fù)雜性分析 2.1.5 遞歸算法的時間復(fù)雜性分析遞歸算法的時間復(fù)雜性分析 1. 猜測技術(shù)猜測技術(shù):對對遞推

13、關(guān)系式估計一個上限，遞推關(guān)系式估計一個上限，然后（用數(shù)學(xué)歸納法）證明它正確。如然后（用數(shù)學(xué)歸納法）證明它正確。如果成功，試著收縮上限。如果失敗，放果成功，試著收縮上限。如果失敗，放松限制再試著證明。直到上限符合要求。松限制再試著證明。直到上限符合要求。v 遞歸算法是分而治之的方法。遞歸算法是分而治之的方法。v 遞歸算法時間復(fù)雜性分析的關(guān)鍵：根據(jù)遞遞歸算法時間復(fù)雜性分析的關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)系式，然后求解這個遞歸過程建立遞推關(guān)系式，然后求解這個遞推關(guān)系式。推關(guān)系式。2. 猜測技術(shù)猜測技術(shù) + + 2)2(221)(nnnTnnT補例補例1 使用猜測技術(shù)分析二路使用猜測技術(shù)分析二路歸并排序

14、算法的時間復(fù)雜性。歸并排序算法的時間復(fù)雜性。二路歸并排序運行時間遞推式：二路歸并排序運行時間遞推式：假定假定T(n)n2，需證明這個猜測是正確的。為方便假定，需證明這個猜測是正確的。為方便假定n=2kT(2)=122成立，對所有成立，對所有in，假設(shè)，假設(shè)T(i)i2，則：，則：T(2n)2T(n)+2n2n2+2n 4n2=(2n)2故得，故得，T(n)=O(n2)成立成立2. 猜測技術(shù)猜測技術(shù) O(n2)是最小上限？如果猜測更小一些，如是最小上限？如果猜測更小一些，如T(n)cn，證明失敗。，證明失敗。即說明上限即說明上限 應(yīng)在應(yīng)在n和和n2之間。之間。再試試再試試T(n)nlognT(2

15、)=1 2log2成立，對所有成立，對所有in，假設(shè)，假設(shè)T(i) nlogn ，則：，則：T(2n)2T(n)+2n2nlogn +2n=2n(logn+1) =2nlog(2n)故得，故得，T(n)=O(nlogn)成立成立2. 擴展遞歸技術(shù)擴展遞歸技術(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+ + + + + + +

16、 + + + + + + + LL例2.7 使用擴展遞歸技術(shù)分析下面遞推式的時間復(fù)雜性為方便假定n=2k。將遞推式進行擴展3. 通用分治遞推式通用分治遞推式大小為大小為n的原問題分成若干個大小為的原問題分成若干個大小為n/b的子問題，的子問題，其中其中a個子問題需要求解，而個子問題需要求解，而cnk是合并各個子問題是合并各個子問題的解需要的工作量。的解需要的工作量。 + + 1)(1)(ncnbnaTncnTk kkkbkkabanObannObanOnTb)()log()()(log定理定理2.1 設(shè)設(shè)T(n)是一個非遞減函數(shù)，且滿足通用分治遞推式，是一個非遞減函數(shù)，且滿足通用分治遞推式，則

17、有如下結(jié)果成立。則有如下結(jié)果成立。 3. 通用分治遞推式通用分治遞推式證明：用擴展遞歸技術(shù)對通用分治遞推式進行推導(dǎo)，假定a=bm211000( )( )()( ) )(1)().( )()()ikkkmmkkkmkmmmm ikm i ikmm iiiinnnT naTcna aTccnbbbnna Tacaccnbbnbcaca bcaab+ +求和是個幾何級數(shù)，比率r=bk/a，且,有以下三種情況：loglogbbnamaan3. 通用分治遞推式通用分治遞推式loglog0logk0101(1)1:,a,( )()1(2)1:1 log n 1,an ,( )(log n)1(3)1:(r

18、 )T(n) O(a)()( )1bbbmaaimimaimkbbimmimmmkmkirrnT nOnrrrmnT nOnrrrOrObOnr+由于所以由于所以，所以，2.2 算法的空間復(fù)雜性分析算法的空間復(fù)雜性分析算法在運行過程中所需的存儲空間包括：算法在運行過程中所需的存儲空間包括：（1）輸入輸出數(shù)據(jù)占用的空間。取決于問題，與算法無關(guān)）輸入輸出數(shù)據(jù)占用的空間。取決于問題，與算法無關(guān)（2）算法本身占用的空間。大小固定）算法本身占用的空間。大小固定（3）執(zhí)行算法需要的輔助空間?？臻g復(fù)雜性所指）執(zhí)行算法需要的輔助空間。空間復(fù)雜性所指S(n)=O(f(n)算法輸入輸出數(shù)據(jù)輔助空間2.2 算法的空

19、間復(fù)雜性分析算法的空間復(fù)雜性分析例例2.8 分析例分析例2.2中起泡排序算法的空間復(fù)雜性。中起泡排序算法的空間復(fù)雜性。解：輸入輸出都在解：輸入輸出都在rn中，聲明了中，聲明了3個簡單變量：個簡單變量：exchange、bound和和temp。所以空間復(fù)雜性為。所以空間復(fù)雜性為O(1)如果算法所需的輔助空間相對于問題的輸入規(guī)模來說是一個常如果算法所需的輔助空間相對于問題的輸入規(guī)模來說是一個常數(shù)，我們稱此算法為原地（或就地）工作。起泡排序算法屬于數(shù)，我們稱此算法為原地（或就地）工作。起泡排序算法屬于就地性質(zhì)。就地性質(zhì)。例例2.9 分析例分析例2.3中合并算法的空間復(fù)雜性。中合并算法的空間復(fù)雜性。解

20、：合并不能就地進行，需要將合并結(jié)果存入另外一個數(shù)組中。解：合并不能就地進行，需要將合并結(jié)果存入另外一個數(shù)組中。設(shè)序列設(shè)序列A的長度為的長度為n，序列，序列B的長度為的長度為m，則合并后的有序序列，則合并后的有序序列的長度為的長度為n+m，因此算法的空間復(fù)雜性為，因此算法的空間復(fù)雜性為O(n+m)2.3 最優(yōu)算法最優(yōu)算法同一個問題可能會存在多種算法，是否有求同一個問題可能會存在多種算法，是否有求解該問題的最優(yōu)算法？解該問題的最優(yōu)算法？如果能夠知道一個問題的計算復(fù)雜性如果能夠知道一個問題的計算復(fù)雜性下界下界，也就是求解該問題的任何算法（包括尚未發(fā)現(xiàn)的也就是求解該問題的任何算法（包括尚未發(fā)現(xiàn)的算法）

21、所需的時間下界，就可以較準(zhǔn)確地評價各算法）所需的時間下界，就可以較準(zhǔn)確地評價各種算法的效率，確定算法還有多少改進余地。種算法的效率，確定算法還有多少改進余地。2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界下界下界是指求解問題所需的是指求解問題所需的最少最少工作量。通常工作量。通常采用大采用大（讀歐米伽）表示。例如，已經(jīng)證明基于（讀歐米伽）表示。例如，已經(jīng)證明基于比較的排序算法的時間下界是比較的排序算法的時間下界是(nlog2n)，意味著，意味著不存時間復(fù)雜性小于不存時間復(fù)雜性小于O(nlog2n)的基于比較的排序的基于比較的排序算法。算法。 定義定義2.2 若存在兩個正常數(shù)若存在兩個正常

22、數(shù)c和和n 0 ，對于任意，對于任意nn 0，都有，都有T(n)cg(n)，就稱，就稱T(n) (g(n) 。 2022-6-2Algorithm Introduction27大大符號描述增長率的下限，表示符號描述增長率的下限，表示T(n)的增長至少像的增長至少像g(n)增增長的那樣快。長的那樣快。如果能找到一個盡可能大的函數(shù)如果能找到一個盡可能大的函數(shù)g(n)使得求解該問題的所有使得求解該問題的所有算法都可以在算法都可以在(g(n)時間內(nèi)完成，則稱時間內(nèi)完成，則稱g(n)為該問題的計算為該問題的計算復(fù)雜性下界，如果已經(jīng)知道一個和下界的效率類型相同的算復(fù)雜性下界，如果已經(jīng)知道一個和下界的效率類

23、型相同的算法法 ，則稱該下界是緊密的。，則稱該下界是緊密的。cg(n)T(n)nono之前的情況不重要執(zhí)行次數(shù)問題規(guī)模2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界 定義定義2.3 若存在三個正常數(shù)若存在三個正常數(shù)c1、c2和和n 0 ，對于任意，對于任意nn 0，都有都有c1 f(n) T(n) c2 f(n)，就稱，就稱T(n) (f(n) 。 2022-6-2Algorithm Introduction28符號意味著符號意味著T(n)與與f(n)同階，用來表示算法的精確階。同階，用來表示算法的精確階。問題的計算復(fù)雜性上下界（準(zhǔn)確界）問題的計算復(fù)雜性上下界（準(zhǔn)確界）n0問題規(guī)模問題規(guī)

24、模n執(zhí)執(zhí)行行次次數(shù)數(shù)n0之前之前的情況的情況無關(guān)緊無關(guān)緊要要T( (n) )c2f( (n) )c1f( (n) )2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界例：例：T(n)=3n-1，上界？下界？上下界？，上界？下界？上下界？解：解：當(dāng)當(dāng)n1時，時，3n-13n=(n)當(dāng)當(dāng)n1時，時，3n-1 3n-n=2n=(n)當(dāng)當(dāng)n1時，時， 3n 3n-1 2n，則，則3n-1=(n)2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界大大常與大常與大O配合以證明某問題的一個特定算配合以證明某問題的一個特定算法是該問題的最優(yōu)算法，或是該問題中的某算法法是該問題的最優(yōu)算法，或是該問題中的某算

25、法類中的最優(yōu)算法。一般情況下，如果能證明某問類中的最優(yōu)算法。一般情況下，如果能證明某問題的時間下界是題的時間下界是(g(n)，那么，對以時間，那么，對以時間O(g(n)來求解該問題的任何算法（其實就是確定算法的來求解該問題的任何算法（其實就是確定算法的精確階是精確階是 (g(n)），都認為是求解該問題的最），都認為是求解該問題的最優(yōu)算法。優(yōu)算法。2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界例例2.10 如下算法實現(xiàn)在一個數(shù)組中求最小值元素，如下算法實現(xiàn)在一個數(shù)組中求最小值元素，證明該算法是最優(yōu)算法。證明該算法是最優(yōu)算法。int ArrayMin(int a, int n)int min

26、=a0;for(int i=1;in;i+) if(aimin) min=ai;return min;2.3.1 問題的計算復(fù)雜性下界問題的計算復(fù)雜性下界證明：算法需要進行n-1次比較，時間復(fù)雜性是O(n)。下面要證明問題的下界是(n)，即對于任何n個整數(shù)，求最小值元素至少需要進行n-1次比較。將n個整數(shù)分為三個動態(tài)的集合。任何一個通過比較求最小值元素的算法都要從(n,0,0)狀態(tài)開始，最終到達(0,n-1,1)。這個過程實際上是將元素從A向B和C移動，但每次比較，至多能把一個較大元素從集合A移向集合B，因此，任何求最小值算法至少要進行n-1次比較，其時間下界是(n)。所以算法是最優(yōu)算法。初始

27、狀態(tài)(n,0,0)完成狀態(tài)(0,n-1,1)算法運行確定和證明某個問題的計算復(fù)雜性下界是很困難的，因為不可能枚舉該問題的所有算法。事實中，存在大量問題，它們的下界是不清楚的。2.3.2 平凡下界平凡下界平凡下界：使用平凡下界：使用計數(shù)計數(shù)方法得出的算法復(fù)雜性下界。即方法得出的算法復(fù)雜性下界。即對問題的輸入中必須要處理的元素進行計數(shù)，同時對必須對問題的輸入中必須要處理的元素進行計數(shù)，同時對必須要輸出的元素進行計數(shù)，得到一個平凡下界。要輸出的元素進行計數(shù)，得到一個平凡下界。例如，任何生成例如，任何生成n個不同元素的所有排列對象的算法個不同元素的所有排列對象的算法必定屬于必定屬于(n!)，因為輸出的

28、規(guī)模就是，因為輸出的規(guī)模就是n！平凡下界很容易得出，但往往過小而失去意義。例如，平凡下界很容易得出，但往往過小而失去意義。例如，TSP問題的平凡下界是問題的平凡下界是(n!)，但沒有意義，至今沒有找到，但沒有意義，至今沒有找到一個多項式時間算法。一個多項式時間算法。2.3.3 判定樹模型判定樹模型許多算法的工作方式都是對輸入元素進行許多算法的工作方式都是對輸入元素進行比較比較，例如排序，例如排序和查找算法，故可以用和查找算法，故可以用判定樹判定樹來研究這些算法的時間性能。來研究這些算法的時間性能。判定樹：滿足如下條件的二叉樹：判定樹：滿足如下條件的二叉樹：（1）每個內(nèi)部結(jié)點對應(yīng)形如）每個內(nèi)部結(jié)

29、點對應(yīng)形如xy的比較，根據(jù)關(guān)系成立與的比較，根據(jù)關(guān)系成立與否，控制轉(zhuǎn)移到左右子樹；否，控制轉(zhuǎn)移到左右子樹；（2）每個葉子結(jié)點表示問題的一個結(jié)果。從根到葉子結(jié)點）每個葉子結(jié)點表示問題的一個結(jié)果。從根到葉子結(jié)點所走過的路徑代表算法執(zhí)行的過程，路徑的長度即代表算所走過的路徑代表算法執(zhí)行的過程，路徑的長度即代表算法執(zhí)行的時間法執(zhí)行的時間2.3.3 判定樹模型判定樹模型例例2.11 用判定樹模型求解排序問題的時間下界。用判定樹模型求解排序問題的時間下界。解：根據(jù)排序算法中的比較，建立起判定樹來描述算法，解：根據(jù)排序算法中的比較，建立起判定樹來描述算法，則判定樹的高度就是算法的下界。則判定樹的高度就是算法

30、的下界。補充材料：補充材料：算法的實驗分析算法的實驗分析 漸進分析能夠在數(shù)量級上對算法進行精確度量，但數(shù)漸進分析能夠在數(shù)量級上對算法進行精確度量，但數(shù)學(xué)不是萬能的，許多貌似簡單的算法很難用數(shù)學(xué)的精學(xué)不是萬能的，許多貌似簡單的算法很難用數(shù)學(xué)的精確性和嚴格性來分析，尤其在做確性和嚴格性來分析，尤其在做平均效率平均效率分析時。分析時。 算法的算法的實驗分析實驗分析是一種事后計算的方法，通常需要將是一種事后計算的方法，通常需要將算法轉(zhuǎn)換為對應(yīng)的程序并上機運行。例如可在程序中算法轉(zhuǎn)換為對應(yīng)的程序并上機運行。例如可在程序中設(shè)置計數(shù)器變量來記錄基本語句的執(zhí)行次數(shù)。設(shè)置計數(shù)器變量來記錄基本語句的執(zhí)行次數(shù)。vo

31、id SubbleSort(int r, int n)int count1,count2=0;int bound,exchange=n-1;while(exchange!=0)/當(dāng)上一趟排序有記錄交換時當(dāng)上一趟排序有記錄交換時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“移動次數(shù)是移動次數(shù)是”count2endl;2022-6-2Algorithm Introduction37補充材料補充材料 算法的實驗分析算法