第1章算法分析的基本概念和方法ppt課件

1、內(nèi)容提要內(nèi)容提要 一、算法及其特性二、算法的時間空間復(fù)雜度三、算法分析(AlgorithmAnalysis)1.分析算法時間復(fù)雜度的基本步驟2.算法時間復(fù)雜度的有關(guān)概念3.分析、求解算法復(fù)雜度的方法四、最優(yōu)算法(optimalalgorithm)知識要點知識要點 v算法分析的概念v復(fù)雜度漸近表示的記號：O,v平均時間復(fù)雜度，最壞時間復(fù)雜度，最好時間復(fù)雜度v最優(yōu)算法v分析算法復(fù)雜度的基本方法v分析算法時間復(fù)雜度的步驟v基本運算執(zhí)行頻數(shù)的統(tǒng)計方法v數(shù)學(xué)知識：求和公式、定積分近似求和、遞歸方程的求解學(xué)習(xí)要求學(xué)習(xí)要求 v掌握算法復(fù)雜度的基本概念v熟悉算法復(fù)雜度分析的基本方法1.1算法及其特性算法及其特

2、性 v一、一、 算法算法(algorithm) v算法就是一組有窮的規(guī)則，它們規(guī)算法就是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問題的一系列運算。定了解決某一特定類型問題的一系列運算。v二、算法的五個特性二、算法的五個特性v確定性確定性 v能行性能行性 v有窮性有窮性 v輸入輸入 v輸出輸出 1.1算法及其特性算法及其特性衡量算法性能一般有下面幾個標準：確定性易讀性健壯性算法的時間和空間性能：高效率和低存儲空間本課程中主要討論算法的時間和空間性能，并以此作為衡量算法性能的重要標準，而且主要側(cè)重于時間方面。三、衡量算法性能的標準1.2. 算法的時間空間復(fù)雜度算法的時間空間復(fù)雜度 v算法的時間復(fù)

3、雜度：在算法運行期間所花費的時間。 v通常用漸進形式表示。比如，T(n)= O (n2)、 (n2) 或 (n2) 一、算法的時間復(fù)雜度(Time Complexity)1.2. 算法的時間空間復(fù)雜度算法的時間空間復(fù)雜度v算法的空間復(fù)雜度：在算法運行期間所需要的內(nèi)存空間，通常指除開容納輸入數(shù)據(jù)之外的附加空間auxiliaryspace,orworkspace）。v通常用漸進形式表示。比如，S(n)=O(n2)、(n2)或(n2)二、算法的空間復(fù)雜度(Space Complexity) 1.2. 算法的時間空間復(fù)雜度算法的時間空間復(fù)雜度v算法分析是指對于計算機算法的時間和空間復(fù)雜度進行定量的分析

4、。為了確切起見，假定執(zhí)行算法的計算機是滿足如下條件的“通用型計算機：v順序處理機：每次執(zhí)行程序中的一條指令；vRAM足夠大；v在固定的時間內(nèi)可把一個數(shù)從一個單元取出或者存入。v下面將學(xué)習(xí)算法分析的主要內(nèi)容：v分析算法時間復(fù)雜度的基本步驟v算法時間復(fù)雜度的有關(guān)概念v分析、求解算法復(fù)雜度的數(shù)學(xué)知識三、 算法分析 (Algorithm Analysis) 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟 v對算法的分析必須脫離具體的計算機結(jié)構(gòu)和程序設(shè)計語言。因而，比較兩個算法的好壞，看其中所需的運算時間的長短是由算法所需的運算次數(shù)決定的。任何一個算法都可能有幾種運算，因而，我們抓住其中影響算法運行

5、時間最大的運算作為基本運算。如在一個字表中尋找Z的問題，把Z和表中元素的比較作為基本運算。兩個實數(shù)矩陣相乘的問題中，則把兩個實數(shù)相乘作為基本運算。一、選取一種運算作為基本運算(basic operation) 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟v一個計算步驟，如果其時間耗費總是不超過某個常量，而與輸入和算法無關(guān)，則稱之為元運算。元運算(elementary operation) 常見的元運算 v算術(shù)運算：加、減、乘、除；v比較和邏輯運算；v賦值運算，包括指針賦值比如，在遍歷表或樹時的指針賦值）；等等。1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟同一個問題對不同的輸入，基本

6、運算的次數(shù)亦可能不同。因而，我們引進問題大小即規(guī)模，size的概念。例如，在一個姓名表中尋找給定的Z的問題，問題的大小可用表中姓名的數(shù)目表示。對于兩個實數(shù)矩陣相乘的問題，其大小可用矩陣的階來表示。而對于遍歷一棵二叉樹的問題，其大小是用樹中結(jié)點數(shù)來表示等等。這樣，一個算法的基本運算的次數(shù)就可用問題的大小n的函數(shù)f(n)來表示。二、表示出在算法運行期間基本運算執(zhí)行的總頻數(shù) 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟v在一個算法中，出現(xiàn)的頻數(shù)最高在相差一個常數(shù)因子的意義上的元運算稱為基本元算?；具\算(basic operation) 常見的基本運算 v當分析查找和排序的算法時，如果元素的比

7、較是元運算，則可作為基本運算；v在矩陣乘法的算法中，數(shù)的乘法可作為基本運算；v當遍歷鏈表時，給指針賦值或者更新指針的操作可作為基本運算；v在圖的遍歷中，可以將訪問節(jié)點的操作為基本運算；等等。1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟在實際中精確地求一個算法的基本運算次數(shù)f(n)等于多少，往往不容易，甚至有時根本不可能，有些即使求出結(jié)果很長，很繁瑣，不易比較，需要簡化。這時候我們可以不精確地估計f(n)。此外，我們分析算法的時間目的主要在于，能區(qū)分不同算法的優(yōu)劣，在n很小時候，差別不大，隨著n的逐漸增大，差別越來越大，是個極限行為?；谏鲜鲈?，引進下面漸近表示的方法。復(fù)雜度漸近表示可以

8、將簡潔地表示出復(fù)雜度的數(shù)量級別。三 、漸近時間復(fù)雜度(asymptotic time complexity) 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟v設(shè)f(n)和g(n)均是從自然數(shù)集到非負實數(shù)集上的函數(shù)。如果存在常數(shù)c0和一個自然數(shù)n0，使得對于任意的nn0，均有f(n)cg(n),則f(n)=O(g(n)。v含義：階至多為g(n)的函數(shù)，即上限。v讀法：O(g(n)讀作“大Ohg(n)”。1. O-記號 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟v設(shè)f(n)和g(n)均是從自然數(shù)集到非負實數(shù)集上的函數(shù)。如果存在常數(shù)c0和一個自然數(shù)n0，使得對于任意的nn0，均有f(n)

9、cg(n),那么，f(n)=(g(n)。v含義：階至少為g(n)的函數(shù)，即下限。v讀法：(g(n)讀作“omegag(n)”。2. -記號 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟v設(shè)f(n)和g(n)均是從自然數(shù)集到非負實數(shù)集上的函數(shù)。如果存在一個自然數(shù)n0和兩個正常數(shù)c1，c2，使得對于任意的nn0，均有c1g(n)f(n)c2g(n),那么，f(n)=(g(n)。v含義：階恰好為g(n)的函數(shù)。v讀法：(g(n)讀作“thetag(n)”。 3. -記號 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟例例1 設(shè)設(shè)f(n)=10n2+20n。則有。則有 f(n)=O(n2)

10、f(n)=(n2) f(n)= (n2) 例例2 設(shè)設(shè)f(n)=aknk+ak-1nk-1+a1n+ a0 ,(ak0)。則有。則有 f(n)=O(nk) f(n)=(nk) f(n)= (nk) 四、舉例 1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟例例3 設(shè)設(shè)f(n)= 2n ，g(n)= n! 。則有。則有 f(n)=O(g(n) 但是，但是，f(n)(g(n) 因而，因而，f(n) (g(n) 此時，記作此時，記作O(f(n) O(g(n)。 四、舉例1.3. 分析復(fù)雜度的基本步驟分析復(fù)雜度的基本步驟各種復(fù)雜度比較示意圖如下。五、復(fù)雜度比較示意圖 1.3. 分析復(fù)雜度的基本步驟分

11、析復(fù)雜度的基本步驟各種復(fù)雜度比較示意圖如下。五、復(fù)雜度比較示意圖 1.4. 復(fù)雜度的有關(guān)概念復(fù)雜度的有關(guān)概念 一、算法時間復(fù)雜度 v對于算法的時間復(fù)雜度，通常從分平均、最壞、最好幾種情形來衡量，尤其是前兩種。v算法的平均復(fù)雜性設(shè)Dn是對于所考慮問題來說大小為n的輸入的集合，并設(shè)i是Dn的一個元素，p(i)是i出現(xiàn)的概率，t(i)是算法在輸入i時所執(zhí)行的基本運算次數(shù)。那么，算法的平均復(fù)雜性定義為：A(n)=iDnp(i)t(i)v算法的最壞復(fù)雜性W(n)=MAXiDnt(i)v算法的最好復(fù)雜性B(n)=MINiDnt(i)1.4. 復(fù)雜度的有關(guān)概念復(fù)雜度的有關(guān)概念例例1 檢索問題的順序查找算法檢

12、索問題的順序查找算法1.1。 以元素的比較作為基本操作。考慮成功檢索的情況。以元素的比較作為基本操作?？紤]成功檢索的情況。 最好情況下的時間復(fù)雜度：最好情況下的時間復(fù)雜度： (1) 最壞情況下的時間復(fù)雜度：最壞情況下的時間復(fù)雜度： (n) 在等概率前提下，平均情況下的時間復(fù)雜度：在等概率前提下，平均情況下的時間復(fù)雜度： (n)二、舉例算法分析方法算法分析方法v例：順序搜索算法例：順序搜索算法templateintseqSearch(Type*a,intn,Typek)for(inti=0;in;i+)if(ai=k)returni;return-1;（1Tmax(n)=maxT(i)|size

13、(i)=n=O(n)（2Tmin(n)=minT(i)|size(i)=n=O(1)（3在平均情況下，假設(shè)：(a)搜索成功的概率為p(0p1)；(b)在數(shù)組的每個位置i(0in)搜索成功的概率相同，均為p/n。nIsizeavgITIpnT)()()()(pnnpnnpnpnp1321)1 (2) 1(11pnnppninpni1.4. 復(fù)雜度的有關(guān)概念復(fù)雜度的有關(guān)概念例例2 直接插入排序算法直接插入排序算法1.5。 以元素的比較作為基本操作。以元素的比較作為基本操作。 最好情況下的時間復(fù)雜度：最好情況下的時間復(fù)雜度： (n) 最壞情況下的時間復(fù)雜度：最壞情況下的時間復(fù)雜度：在等概率前提下，平

14、均情況下的時間復(fù)雜度：在等概率前提下，平均情況下的時間復(fù)雜度：二、舉例)(2n)(2n算法分析的基本法則算法分析的基本法則v非遞歸算法：非遞歸算法：v（1for / while 循環(huán)循環(huán)v循環(huán)體內(nèi)計算時間循環(huán)體內(nèi)計算時間*循環(huán)次數(shù)；循環(huán)次數(shù)；v（2嵌套循環(huán)嵌套循環(huán)v循環(huán)體內(nèi)計算時間循環(huán)體內(nèi)計算時間*所有循環(huán)次數(shù)；所有循環(huán)次數(shù)；v（3順序語句順序語句v各語句計算時間相加；各語句計算時間相加；v（4if-else語句語句vif語句計算時間和語句計算時間和else語句計算時間的較大者。語句計算時間的較大者。templatevoidinsertion_sort(Type*a,intn)Typekey;

15、/costtimesfor(inti=1;i=0&ajkey)/c4sumoftiaj+1=aj;/c5sumof(ti-1)j-;/c6sumog(ti-1)aj+1=key;/c7n-1v在最好情況下，ti=1,for1in;v在最壞情況下，tii+1,for1i=2) return F(n-1)+F(n-2); v v解：該算法的計算時間解：該算法的計算時間T(n)滿足遞歸方程：滿足遞歸方程： v T(n)=T(n-1)+T(n-2)+1, n1； v 初始條件初始條件 T(0)=T(1)=0。 1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法例例3 用平攤的辦法來統(tǒng)計基本

16、操作的次數(shù)用平攤的辦法來統(tǒng)計基本操作的次數(shù)Amortized Analysis）(1.13) 整型數(shù)組整型數(shù)組A(1：n)初始化為初始化為n個正整數(shù)的集合個正整數(shù)的集合,雙鏈表雙鏈表List初始化為僅含一個初始化為僅含一個元素元素0 for(j=1;j=n;j+) x=A(j); 將將 x 插入到表插入到表List尾尾 if x 是偶數(shù)是偶數(shù) then while 表表List中中x的前面元素為奇數(shù)的前面元素為奇數(shù) 在表在表List中刪除中刪除x的前面的那個元素的前面的那個元素 end while end if end for v解：算法的基本操作為元素的插入和刪除操作。算法中插入解：算法的基

17、本操作為元素的插入和刪除操作。算法中插入操作的次數(shù)為操作的次數(shù)為 n 次，而刪除操作的次數(shù)最多為次，而刪除操作的次數(shù)最多為n-1次，所以，次，所以，算法的基本操作最少算法的基本操作最少n次，最多次，最多2n-1次。次。1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法1典型的求和公式0inf(i)二、求解算法復(fù)雜度的基本方法 1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法2.積分近似求和如果連續(xù)函數(shù)f(n)是單調(diào)遞減的，則有如果連續(xù)函數(shù)f(n)是單調(diào)遞增的，則有1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法1.5. 分析

18、和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法遞歸是一種重要的程序設(shè)計方法。有些問題的算法運用遞歸過程來表示不僅自然簡潔，而且也易于驗證其正確性。遞歸算法的特點就是：易讀，易寫，易證。遞歸和歸納緊密相關(guān)。歸納定義的東西往往易寫出其遞歸的算法；而遞歸的算法往往可用歸納法來證明。遞歸算法的時間復(fù)雜度分析往往需要借助于求解遞歸方程或者遞歸不等式的解得到。遞歸方程的類型較多，涉及到的數(shù)學(xué)知識也較多。這里我們僅簡單地介紹分析算法復(fù)雜度時常見的幾類簡單遞歸方程的求法。三、遞歸關(guān)系 1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法常用方法：展開法、差分方程法、換元法、數(shù)學(xué)歸納法等。三、遞歸關(guān)系 1.5. 分析和求解復(fù)雜度的方法分析和求解復(fù)雜度的方法（1） 線性非齊次遞歸方程線性非齊次遞歸方程 主要解法：差分方程法、數(shù)學(xué)歸納法等。主要解法：差分方程法、數(shù)學(xué)歸納法等。1.5