計算機算法設計與分析第1章算法概述課件

1、1理論課：理論課：110周，周，40學時學時 周二周二(5-6)、周五、周五(1-2)上機：上機： 18學時學時期末考試：期末考試： 閉卷筆試，第閉卷筆試，第 11周周上課點名三次不到者取消考試資格；上課點名三次不到者取消考試資格；遲到或作業(yè)缺交，一次扣遲到或作業(yè)缺交，一次扣10分（平時成績）。分（平時成績）。2本課程是計算機類專業(yè)計算機類專業(yè)的專業(yè)基礎課程；通過課程學習和上機實踐課程學習和上機實踐，對計算機常用算法有一個較全面的了解，掌握通用算法的一般設計方法；學會對算法的時間算法的時間、空間復雜度分析空間復雜度分析，掌握提高算法效率的方法提高算法效率的方法和途徑。3（一）（一） 從理論和實

2、踐的角度理解從理論和實踐的角度理解 計算機科學的基石；掌握標準算法計算機科學的基石；掌握標準算法（二）從算法（二）從算法對于對于程序的重要性來講程序的重要性來講 皮之不存，毛將附焉？皮之不存，毛將附焉？（三）（三） 從對同學們的能力培養(yǎng)看從對同學們的能力培養(yǎng)看 開發(fā)分析問題的能力開發(fā)分析問題的能力4（一）數(shù)據(jù)結構關心的對象（一）數(shù)據(jù)結構關心的對象 各種各種數(shù)據(jù)結構數(shù)據(jù)結構的作用和效率、具體的問題的作用和效率、具體的問題（二）算法設計與分析關心的對象（二）算法設計與分析關心的對象 算法算法設計技術設計技術的適用性和效率、的適用性和效率、一般性方一般性方法法5第第1 1章章 算法概述算法概述第第2

3、 2章章 遞歸與分治策略遞歸與分治策略第第3 3章章 動態(tài)規(guī)劃動態(tài)規(guī)劃第第4 4章章 貪心算法貪心算法第第5 5章章 回溯法回溯法第第6 6章章 分支限界法分支限界法* *7-97-9章屬研究生學習內容，可自學了解章屬研究生學習內容，可自學了解。6學習要點學習要點: 一、一、理解算法的概念，以及問題求解的理解算法的概念，以及問題求解的過程。過程。二、二、掌握算法的幾種描述方式。掌握算法的幾種描述方式。三、三、理解算法的計算復雜性概念。理解算法的計算復雜性概念。四、四、掌握算法漸近復雜性的數(shù)學表述。掌握算法漸近復雜性的數(shù)學表述。7我們來編寫一個燒開水的算法：輸入輸入自來水循環(huán)循環(huán)（反復）加熱直到

4、水開輸出輸出開水8 算法概念算法概念：通俗地講，算法是指解決問題通俗地講，算法是指解決問題的一種方法或一個過程。嚴格地講，算法是的一種方法或一個過程。嚴格地講，算法是由若干條指令組成的有窮序列。由若干條指令組成的有窮序列。輸入輸出算法問題“計算設備”91、算法具有某些特性，如下幾條：、算法具有某些特性，如下幾條：(1)輸入輸入：有零個或多個外部提供的量作為算：有零個或多個外部提供的量作為算法的輸入。法的輸入。(2)輸出輸出：算法產(chǎn)生至少一個量作為輸出。這：算法產(chǎn)生至少一個量作為輸出。這些輸出是和輸入有某種特定關系的量。些輸出是和輸入有某種特定關系的量。10(3)確定性確定性：組成算法的每條指令

5、是清晰，無：組成算法的每條指令是清晰，無歧義的。歧義的。(4)有限性（有窮性）有限性（有窮性）：算法中每條指令的執(zhí)：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時間也是行次數(shù)是有限的，執(zhí)行每條指令的時間也是有限的。有限的。11(5)可實現(xiàn)性可實現(xiàn)性：此性質是指算法中有待實現(xiàn)的此性質是指算法中有待實現(xiàn)的運算都是相當基本的，每種運算至少在原理運算都是相當基本的，每種運算至少在原理上能由人用紙和筆在有限的時間內完成。上能由人用紙和筆在有限的時間內完成。（補充）（補充）122、關于算法有幾個要點：、關于算法有幾個要點：(1) 算法所處理的輸入的值域必須嚴格定義。算法所處理的輸入的值域必須嚴格定義。

6、(2) 同樣一種算法可以用幾種不同的形式來描同樣一種算法可以用幾種不同的形式來描述。述。13(3) 同一個問題可以存在多種解決的算法。同一個問題可以存在多種解決的算法。(4) 同一個問題的幾種算法可能會基于完全不同一個問題的幾種算法可能會基于完全不同的解題思路，而且解題速度也會有顯著不同的解題思路，而且解題速度也會有顯著不同。同。141)問題的陳述 用科學規(guī)范的語言用科學規(guī)范的語言,對所求解的問題做準確的對所求解的問題做準確的描述描述.2)建立數(shù)學模型 通過對問題的分析通過對問題的分析,找出其中的所有操作對象找出其中的所有操作對象及操作對象之間的關系并用數(shù)學語言加以描及操作對象之間的關系并用數(shù)

7、學語言加以描述述.3)算法設計算法設計 根據(jù)數(shù)學模型設計問題的計算機求解算法根據(jù)數(shù)學模型設計問題的計算機求解算法.154)算法的正確性證明算法的正確性證明 證明算法對一切合法輸入均能在有限次計算證明算法對一切合法輸入均能在有限次計算后產(chǎn)生正確輸出后產(chǎn)生正確輸出.5)算法的程序實現(xiàn) 將算法正確地編寫成機器語言程序將算法正確地編寫成機器語言程序.6)算法分析算法分析 對執(zhí)行該算法所消耗的計算機資源進行估算對執(zhí)行該算法所消耗的計算機資源進行估算.16通過學習已被實踐證明是有用的一些基本設通過學習已被實踐證明是有用的一些基本設計策略，如遞歸、回溯等，掌握一般的算法計策略，如遞歸、回溯等，掌握一般的算法

8、設計方法，學會設計高效的算法。設計方法，學會設計高效的算法。17證明算法對所有可能的輸入都能算出正確的證明算法對所有可能的輸入都能算出正確的答案，這一工作稱為答案，這一工作稱為算法確認算法確認。這一領域是。這一領域是當前許多計算機工作者集中研究的對象，還當前許多計算機工作者集中研究的對象，還處于相當初期的階段。處于相當初期的階段。在學習本課程中，我們僅對算法的正確性進在學習本課程中，我們僅對算法的正確性進行一般的非形式化討論，以及對算法的程序行一般的非形式化討論，以及對算法的程序實現(xiàn)進行測試驗證。實現(xiàn)進行測試驗證。18分析算法包括分析算法包括 定量的分析算法需要多少定量的分析算法需要多少計算計

9、算時間時間和和存儲空間存儲空間，分析算法不僅可以預計，分析算法不僅可以預計 算算法能否有效得完成任務，而且可以知道算法法能否有效得完成任務，而且可以知道算法在在最壞最壞、最好最好和和平均情況平均情況下的運算時間，對下的運算時間，對解決同一問題解決同一問題的的不同算法不同算法的優(yōu)劣作出比較。的優(yōu)劣作出比較。191、計算兩個整數(shù)的最大公約數(shù)問題的一個現(xiàn)、計算兩個整數(shù)的最大公約數(shù)問題的一個現(xiàn)代數(shù)學術語表述代數(shù)學術語表述 歐幾里得算法基于的方法是重復應用下列歐幾里得算法基于的方法是重復應用下列等式：等式： gcd (m , n) = gcd (n , m mod n) ， 直到直到m mod n等于等

10、于0。gcd(60,24)=gcd(24,12)=gcd(12,0)=12注：gcd (m , 0) =m，m mod n 表示m除以n之后的余數(shù)，稱為模運算20計算計算gcd（m，n）的歐幾里得算法：）的歐幾里得算法：第一步：如果第一步：如果n=0,返回返回m的值作為結果，同的值作為結果，同時過程結束；否則，進入第二步。時過程結束；否則，進入第二步。第二步：用第二步：用n去除去除m，將余數(shù)賦給，將余數(shù)賦給r。第三步：將第三步：將n的值賦給的值賦給m，將，將r的值賦給的值賦給n，返，返回第一步?；氐谝徊健?1ALGORITHM Euclid（m，n）/ 計算計算gcd（m，n）/ 輸入：非負整

11、數(shù)輸入：非負整數(shù)m，n，其中，其中m，n不同時為零不同時為零/ 輸出：輸出：m，n的最大公約數(shù)的最大公約數(shù)while n 0 dor m mod nm nn rreturn m22int Euclid（int m，int n）/ 計算計算gcd（m，n）/ 輸入：非負整數(shù)輸入：非負整數(shù)m，n，其中，其中m，n不同時為零不同時為零/ 輸出：輸出：m，n的最大公約數(shù)的最大公約數(shù) int r=0; if(m*n=0) return 0; / m，n不符合輸入規(guī)范時返回不符合輸入規(guī)范時返回0 while (n 0) r = m mod n; m = n; n = r; return m; 23程序流程

12、圖等，不再一一列舉。程序流程圖等，不再一一列舉。24算法復雜性是算法效率的度量，是評價算法優(yōu)劣的算法復雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。重要依據(jù)。算法復雜性的高低體現(xiàn)在運行算法所需要的算法復雜性的高低體現(xiàn)在運行算法所需要的計算機計算機資源，即時間和空間（存儲器）資源資源，即時間和空間（存儲器）資源的多少上。的多少上。算法的時間復雜性算法的時間復雜性T T( (n n) )，空間復雜性，空間復雜性S S( (n n) )。其中其中n n是問題的規(guī)模（輸入大?。Ｊ菃栴}的規(guī)模（輸入大?。?。25本課程主要對本課程主要對算法算法的時的時間復雜性間復雜性進行分析。進行分析。關于算法的復雜性

13、，有兩個問題要弄清楚：關于算法的復雜性，有兩個問題要弄清楚：（1 1）用怎樣的一個）用怎樣的一個量（指標）量（指標）來表達一個算法的來表達一個算法的復雜性；復雜性；（2 2）對于一個算法，怎樣具體）對于一個算法，怎樣具體計算計算它的復雜性。它的復雜性。26算法的算法的最壞最壞、最好最好和和平均平均時間復雜性時間復雜性（1）最壞情況下的時間復雜性）最壞情況下的時間復雜性 Tmax(n) = max T(I) | size(I)=n （2）最好情況下的時間復雜性）最好情況下的時間復雜性 Tmin(n) = min T(I) | size(I)=n 其中其中 size(I)= n 表示表示 I 是規(guī)

14、模為是規(guī)模為n的實例的實例27（3）平均情況下的時間復雜性）平均情況下的時間復雜性 Tavg(n) = 其中其中 p(I) 是實是實 例例I出現(xiàn)的概率。出現(xiàn)的概率。nIsizeITIp)()()(28例：例：順序查找順序查找算法的時間復雜度計算：算法的時間復雜度計算： 已知不重復已知不重復，從小到大排列的從小到大排列的m m個整數(shù)的數(shù)個整數(shù)的數(shù)組組A1.m,m=2K,KA1.m,m=2K,K為正整數(shù)為正整數(shù)。 對于給定的整數(shù)對于給定的整數(shù)c,c,要求找到一個下標要求找到一個下標i,i,使得使得Ai=c.Ai=c.找不到返回找不到返回0 0。 A1AmAi=c29分析分析:問題的規(guī)模為問題的規(guī)模

15、為m設元運算執(zhí)行時間：賦值設元運算執(zhí)行時間：賦值 a, 判斷判斷 t, 加法加法 s設設 c 在在A中查找成功中查找成功30 int search(int A , int m, int c) int i=1; a a while( Aic & icAmid=low) mid=(low+high)/2;mid=(low+high)/2; if( Amid=c) found=1; else if( Amid=2時，時，3n+2=2時，時，10n2 +4n+2 =5時，時，10n2 +5n=4時，時， n2 0，存在正數(shù)和存在正數(shù)和n0 0使得對所有使得對所有n n0有：有：0 f(n)0，

16、存在正數(shù)和存在正數(shù)和n0 0使得對所有使得對所有n n0有：有：0 cg(n) f(n) 等價于等價于 f(n) / g(n) ，as n。f(n) (g(n) g(n) o (f(n) 47例例1：3n+2= o(n2) 。 例例2：10n2+4n+2 = (n) 。48(g(n) = f(n) | 存在正常數(shù)存在正常數(shù)c1,c2和和n0使得對所有使得對所有n n0有：有：c1g(n) f(n) c2g(n) 記號記號適用于同一個函數(shù)適用于同一個函數(shù)g既可以作為函數(shù)既可以作為函數(shù)f的上限的上限也可以作為也可以作為f的下限的情形。的下限的情形。 定理定理1： (g(n) = O (g(n) (

17、g(n) 49例：對于所有對于所有n，有：，有：3n+2= (n)100n+6= (n)10n2 +4n+2 = (n2 ) 62n+n2= (2n) 。50f(n)=O (g(n) f(n)的階不高于的階不高于g(n)的階；的階；f(n)= (g(n) f(n)的階不低于的階不低于g(n)的階；的階；f(n)=(g(n) f(n)與與g(n)同階。同階。課后習題課后習題1-651以下設以下設f(n),g(n)是定義在正數(shù)集上的正函數(shù)：是定義在正數(shù)集上的正函數(shù)：(1) O(f)+O(g）=O(max(f,g)(2) O(f)+O(g）=O(f+g)(3) O(f)O(g） =O(fg)(4)

18、如果如果f(n) =O(g(n), 則則O(f)+O(g)=O(g)(5) O(cf(n)=O(f(n), 其中其中c是一個正的常數(shù)是一個正的常數(shù)(6) f =O(f)52課后習題課后習題1-353圖1.2 時間函數(shù)的增長率54圖1.3 時間函數(shù)的增長率55（一）算法分析的基本法則（一）算法分析的基本法則非遞歸非遞歸算法：算法：（1）for / while 循環(huán)循環(huán)體內計算時間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內計算時間*所有循環(huán)次數(shù)；56（3）順序語句各語句計算時間相加；（4）if-else語句if語句計算時間和else語句計算時間的較大者。57建立算法的基本操作執(zhí)行次數(shù)的建立算法的基本操作執(zhí)行次數(shù)的遞推關系式遞推關系式，然后，然后確定它的增長次數(shù)。確定它的增長次數(shù)。int factorial