算法及算法分析2

1、算法及算法分析 算法算法是對特定問題求解步驟的一種描述，它是指令的有限序列指令的有限序列，其中每一條指令表示一個或多個操作。一個算法應(yīng)滿足以下五個重要特性五個重要特性：1 1有窮性有窮性 2 2確定性確定性 3 3可行性可行性4 4有輸入有輸入 5 5有輸出有輸出算法算法1 1有窮性有窮性 對于任意一組合法輸入值，在執(zhí)行有窮步驟有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在有限時間有限時間內(nèi)完成； 2 2確定性確定性 對于每種情況每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且并且在任何條件下，算法都只有一在任何條件下，算法都只有一

2、條執(zhí)行路徑；條執(zhí)行路徑；例: (1)begin (2)n=1 (3)n=n+1 (4)repeat (3) (5)end例: (1)begin (2)n=1 (3)n=n+1 (4)if n=100 do (5),else repeat(3) (5)output n (6)end3 3可行性可行性 算法中的所有操作都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次實現(xiàn)之；4 4有輸入有輸入 輸入作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中； 5 5有輸出有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息

3、加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。課堂思考例：從n個整數(shù)元素中找出最大值。文字描述流程圖算法設(shè)計的原則算法設(shè)計的原則設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1正確性正確性2. . 可讀性可讀性3健壯性健壯性4高效率與低存儲量需求高效率與低存儲量需求 c c程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以第 c c 層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。 d d程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)

4、據(jù)都能得出滿足要求 的結(jié)果；的結(jié)果；a a程序中不含語法錯誤；程序中不含語法錯誤；b b程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；2. . 可讀性可讀性 算法主要是為了人的閱讀與交流閱讀與交流，其次才是為計算機執(zhí)行。因此算法應(yīng)該易易于人的理解于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試；例：例：a = ab； b = ab； a = ab；3健壯性健壯性 當(dāng)輸入的數(shù)據(jù)當(dāng)輸入的數(shù)據(jù)非法非法時，算法應(yīng)當(dāng)恰當(dāng)時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)地作出反映或進(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出生莫名奇妙的

5、輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。以便在更高的抽象層次上進(jìn)行處理。4高效率與低存儲量需求高效率與低存儲量需求 通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間。兩者都與問題的規(guī)模有關(guān)。 同一問題可以采用多種算法實現(xiàn)。如何同一問題可以采用多種算法實現(xiàn)。如何比較算法執(zhí)行效率？比較算法執(zhí)行效率？ 算法描述的語言不同算法描述的語言不同 算法執(zhí)行的環(huán)境不同算法執(zhí)行的環(huán)境不同 其他因素其他因素 所以不能用絕對執(zhí)行時間進(jìn)行比較所

6、以不能用絕對執(zhí)行時間進(jìn)行比較 算法執(zhí)行時間需通過依據(jù)該算法編制的程序在算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量。其方法通常有兩種：計算機上運行所消耗的時間來度量。其方法通常有兩種：事后統(tǒng)計事后統(tǒng)計：計算機內(nèi)部進(jìn)行執(zhí)行時間和實際占用空間的：計算機內(nèi)部進(jìn)行執(zhí)行時間和實際占用空間的統(tǒng)計。統(tǒng)計。 問題：必須先運行依據(jù)算法編制的程序；依賴問題：必須先運行依據(jù)算法編制的程序；依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。事前分析事前分析：求出該算法的一個時間界限函數(shù)。：求出該算法的一個時間界限函數(shù)。1.3.3 算法效率

7、的度量算法效率的度量與此相關(guān)的因素有：與此相關(guān)的因素有： 依據(jù)算法選用何種策略；依據(jù)算法選用何種策略； 問題的規(guī)模；問題的規(guī)模； 程序設(shè)計的語言；程序設(shè)計的語言； 編譯程序所產(chǎn)生的機器代碼的質(zhì)量；編譯程序所產(chǎn)生的機器代碼的質(zhì)量； 機器執(zhí)行指令的速度；機器執(zhí)行指令的速度； 撇開軟硬件等有關(guān)部門因素，可以認(rèn)為一個特定撇開軟硬件等有關(guān)部門因素，可以認(rèn)為一個特定算法算法“運行工作量運行工作量”的大小，只依賴于問題的規(guī)模的大小，只依賴于問題的規(guī)模（通常用（通常用n n表示），或者說，它表示），或者說，它是問題規(guī)模的函數(shù)是問題規(guī)模的函數(shù)。 算法中算法中基本操作重復(fù)執(zhí)行的次數(shù)基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模

8、是問題規(guī)模n n的某個函數(shù)，其時間量度記作的某個函數(shù)，其時間量度記作 T(n)=O(f(n)T(n)=O(f(n)，稱作，稱作算法的漸近時間復(fù)雜度算法的漸近時間復(fù)雜度( (Asymptotic Time complexityAsymptotic Time complexity) )，簡稱簡稱時間復(fù)雜度時間復(fù)雜度。 一般地，常用一般地，常用最深層循環(huán)內(nèi)最深層循環(huán)內(nèi)的語句中的原操作的語句中的原操作的的執(zhí)行頻度執(zhí)行頻度( (重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù)) )來表示。來表示。 “O”O(jiān)”的定義：的定義： 若若f(n)f(n)是正整數(shù)是正整數(shù)n n的一個函數(shù)，則的一個函數(shù)，則 O(f(n)O(f(n)表

9、示表示 M M0 0 ，使得當(dāng)，使得當(dāng)n n n n0 0時，時，| f(n) | | f(n) | M M | f(n| f(n0 0) | ) | 。表示表示時間復(fù)雜度時間復(fù)雜度的階有：的階有： O(1)O(1) ：常量時間階：常量時間階 O (n)O (n)：線性時間：線性時間階階 O(O(n)n) ：對數(shù)時間階：對數(shù)時間階 O(nO(nn)n) ：線性對數(shù)時：線性對數(shù)時間階間階算法分析應(yīng)用舉例 O (nO (nk k) )： k k2 2 ，k k次方時間階次方時間階例例 兩個兩個n n階方陣的乘法階方陣的乘法 for(i=1for(i=1，i=n; +i)i=n; +i) for(j

10、=1; j=n; +j) for(j=1; j=n; +j) cij=0 ; cij=0 ; for(k=1; k=n; +k) for(k=1; k=n; +k) cij+=aikcij+=aik* *bkj ; bkj ; 由于是一個三重循環(huán)，每個循環(huán)從由于是一個三重循環(huán)，每個循環(huán)從1 1到到n n，則總次數(shù)為：，則總次數(shù)為： n nn nn=nn=n3 3時間復(fù)雜度為時間復(fù)雜度為T(n)=O(nT(n)=O(n3 3) )例例 +x; s=0 ;+x; s=0 ; 將將x x自增看成是基本操作，則語句頻度為，自增看成是基本操作，則語句頻度為，即時間復(fù)雜度為即時間復(fù)雜度為(1) (1) 。

11、如果將如果將s=0s=0也看成是基本操作，則語句頻度為，其時也看成是基本操作，則語句頻度為，其時間復(fù)雜度仍為間復(fù)雜度仍為(1)(1)，即常量階。，即常量階。例例 for(i=1; i=n; +i)for(i=1; i=n; +i) +x; s+=x ; +x; s+=x ; 語句頻度為：語句頻度為：2n2n，其時間復(fù)雜度為：，其時間復(fù)雜度為：O(n) O(n) ，即為線性，即為線性階。階。例例 for(i=1; i=n; +i)for(i=1; i=n; +i)for(j=1; j=n; +j)for(j=1; j=n; +j) +x; s+=x ; +x; s+=x ; 語句頻度為：語句頻度

12、為：2n2n2 2 ，其時間復(fù)雜度為：，其時間復(fù)雜度為：O(nO(n2 2) ) ，即為，即為平方階。平方階。 定理定理：若若A(n)=a A(n)=a m m n n m m +a +a m-1m-1 n n m-1m-1 +a +a1 1n+an+a0 0是一個是一個m m次多項式，則次多項式，則A(n)=O(nA(n)=O(n m m) )例例 for(i=2;i=n;+i)for(i=2;i=n;+i) for(j=2;j=i-1;+j) for(j=2;j=i-1;+j) +x; ai,j=x; +x; ai,j=x; 語句頻度為：語句頻度為： 1+2+3+1+2+3+n-2=(1+

13、n-2) +n-2=(1+n-2) (n-2)/2(n-2)/2 =(n-1)(n-2)/2 =n=(n-1)(n-2)/2 =n2 2-3n+2-3n+2 時間復(fù)雜度為時間復(fù)雜度為O(nO(n2 2) )，即此算法的時間復(fù)雜度為平方，即此算法的時間復(fù)雜度為平方階。階。 一個算法時間為一個算法時間為O(1)O(1)的算法，它的基本運算執(zhí)行的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為零次多項式）來限界。而一個時間為O(nO(n2 2) )的算法則的算法則由一個二次多項式來限界。由一個二次多項式來限

14、界。 以下六種計算算法時間的多項式是最常用的。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：其關(guān)系為： O(1)O(O(1)O(n)O(n)O(nn)O(n)O(nn)O(nn)O(n2 2)O(n)O(n3 3) ) 指數(shù)時間的關(guān)系為：指數(shù)時間的關(guān)系為： O(2O(2n n)O(n!)O(n)O(n!)O(nn n) ) 當(dāng)當(dāng)n n取得很大時，指數(shù)時間算法和多項式時取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，

15、那就取得了一個偉大的成就。間算法，那就取得了一個偉大的成就。 有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。還隨問題的輸入數(shù)據(jù)集不同而不同。例例1 1：素數(shù)的判斷算法。素數(shù)的判斷算法。Void prime( int n)Void prime( int n)/ /* * n n是一個正整數(shù)是一個正整數(shù) * */ / int i=2 ; int i=2 ; while ( (n% i)!=0 & iwhile ( (n% i)!=0 & i* *1.0 sqrt(n) ) 1.0sqrt(n) )1.0sqrt(n)

16、 )printf(“&d printf(“&d 是一個素數(shù)是一個素數(shù)n” , n) ;n” , n) ;elseelseprintf(“&d printf(“&d 不是一個素數(shù)不是一個素數(shù)n” , n) ;n” , n) ; 嵌套的最深層語句是嵌套的最深層語句是i+i+；其頻度由條件；其頻度由條件( (n% ( (n% i)!=0 & ii)!=0 & i* *1.0 sqrt(n) ) 1.0 sqrt(n) ) 決定，顯然決定，顯然i i* *1.0 1.01 & change; -i)for (i=n-1; change=TURE;

17、 i1 & change; -i)for (j=0; ji; +j)for (j=0; jaj+1) if (ajaj+1) aj aj+1 ; aj aj+1 ; change=TURE ; change=TURE ; 最好情況：最好情況：0 0次次 最壞情況：最壞情況：1+2+3+1+2+3+ +n-1=n(n-1)/2+n-1=n(n-1)/2 平均時間復(fù)雜度為：平均時間復(fù)雜度為： O(nO(n2 2) ) 空間復(fù)雜度空間復(fù)雜度( (Space complexitySpace complexity) ) ：是指算法：是指算法編寫成程序后，在計算機中運行時所需存儲空間大小編寫成程序

18、后，在計算機中運行時所需存儲空間大小的度量。記作：的度量。記作： S(n)=O(f(n) S(n)=O(f(n) 其中：其中： n n為問題的規(guī)模為問題的規(guī)模( (或大小或大小) )該存儲空間一般包括三個方面：該存儲空間一般包括三個方面： 指令常數(shù)變量所占用的存儲空間指令常數(shù)變量所占用的存儲空間; ; 輸入數(shù)據(jù)所占用的存儲空間輸入數(shù)據(jù)所占用的存儲空間; ; 輔助輔助( (存儲存儲) )空間。空間。 一般地，算法的一般地，算法的空間復(fù)雜度空間復(fù)雜度指的是指的是輔助空間輔助空間。 一維數(shù)組一維數(shù)組anan： 空間復(fù)雜度空間復(fù)雜度 O(n)O(n) 二維數(shù)組二維數(shù)組anmanm： 空間復(fù)雜度空間復(fù)雜

19、度 O(nO(n* *m)m)1.3.4 算法的空間分析算法的空間分析例，有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于例，有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于50），），每個學(xué)生數(shù)據(jù)包含學(xué)號（每個學(xué)生學(xué)號是惟每個學(xué)生數(shù)據(jù)包含學(xué)號（每個學(xué)生學(xué)號是惟一的，但學(xué)生記錄不一定按學(xué)號順序存放）、一的，但學(xué)生記錄不一定按學(xué)號順序存放）、姓名、班號和若干門課程成績（每個學(xué)生所姓名、班號和若干門課程成績（每個學(xué)生所選課程數(shù)目可能不等，但最多不超過選課程數(shù)目可能不等，但最多不超過6門）。門）。要求設(shè)計一個程序輸出每個學(xué)生的學(xué)號、要求設(shè)計一個程序輸出每個學(xué)生的學(xué)號、姓名和平均分以及每門課程（課程編號從姓名和平均分以及每門課程（課程編號從16

20、）的平均分。）的平均分。設(shè)計方案設(shè)計方案1 1：將學(xué)生的全部數(shù)據(jù)項放在一個：將學(xué)生的全部數(shù)據(jù)項放在一個表中，一個學(xué)生的全部數(shù)據(jù)對應(yīng)一條記錄。由于表中，一個學(xué)生的全部數(shù)據(jù)對應(yīng)一條記錄。由于課程最多可選課程最多可選6 6門，對應(yīng)的成績項也應(yīng)有門，對應(yīng)的成績項也應(yīng)有6 6個。對個。對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：struct stud int no;/*學(xué)號學(xué)號*/char name10;/*姓名姓名*/int bno;/*班號班號*/int deg1;/*課程課程1分?jǐn)?shù)分?jǐn)?shù)*/int deg2;/*課程課程2分?jǐn)?shù)分?jǐn)?shù)*/int deg3;/*課程課程3分?jǐn)?shù)分?jǐn)?shù)*/int deg4;/*課程課

21、程4分?jǐn)?shù)分?jǐn)?shù)*/int deg5;/*課程課程5分?jǐn)?shù)分?jǐn)?shù)*/int deg6;/*課程課程6分?jǐn)?shù)分?jǐn)?shù)*/;nonamebnodeg1deg2deg3deg4deg5deg61張斌張斌99017882639285838劉麗劉麗9902659572788079特點：特點：存儲空間：中（若學(xué)生沒有選該課程，對應(yīng)空間仍存在）存儲空間：中（若學(xué)生沒有選該課程，對應(yīng)空間仍存在）算法時間：少算法時間：少算法簡潔性差：算法完全依賴數(shù)據(jù)結(jié)構(gòu)算法簡潔性差：算法完全依賴數(shù)據(jù)結(jié)構(gòu)設(shè)計方案設(shè)計方案2 2：將學(xué)生的全部數(shù)據(jù)項放在一個表：將學(xué)生的全部數(shù)據(jù)項放在一個表中，但一個學(xué)生的一門課程成績對應(yīng)一條記錄。中，但一個學(xué)生的

22、一門課程成績對應(yīng)一條記錄。這樣成績項只需要一個，為了區(qū)分不同課程成績，這樣成績項只需要一個，為了區(qū)分不同課程成績，需增加一個課程編號項。對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：需增加一個課程編號項。對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：struct stud int no;/*學(xué)號學(xué)號*/char name10;/*姓名姓名*/int bno;/*班號班號*/int cno;/*課程編號課程編號*/int deg;/*課程分?jǐn)?shù)課程分?jǐn)?shù)*/;nonamebnocnodeg1張斌張斌99011781張斌張斌99012821張斌張斌99013631張斌張斌99014921張斌張斌99015851張斌張斌99016838劉麗劉麗99021

23、658劉麗劉麗99022958劉麗劉麗99023728劉麗劉麗99024788劉麗劉麗99025808劉麗劉麗9902679特點：特點：存儲空間：大存儲空間：大算法時間：多算法時間：多算法簡潔性：好算法簡潔性：好設(shè)計方案設(shè)計方案3 3：將學(xué)生的學(xué)號、姓名和班號放：將學(xué)生的學(xué)號、姓名和班號放在一個表中，將成績數(shù)據(jù)放在另一個表中，兩者在一個表中，將成績數(shù)據(jù)放在另一個表中，兩者通過學(xué)號關(guān)聯(lián)。前者一個學(xué)生對應(yīng)一個記錄，后通過學(xué)號關(guān)聯(lián)。前者一個學(xué)生對應(yīng)一個記錄，后者一門課程成績對應(yīng)一條記錄。對應(yīng)的數(shù)據(jù)結(jié)構(gòu)者一門課程成績對應(yīng)一條記錄。對應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：如下：struct stud1 int no;/*學(xué)號學(xué)號*/char name10;/*姓名姓名*/int bno;/*班號班號*/;struct stud2 int no;/*學(xué)號學(xué)號*/int cno;/*課程編號課程編號*/int deg;/*分?jǐn)?shù)分?jǐn)?shù)*/;nonamebno1張斌張斌99018劉麗劉麗9902no