算法效率分析基礎(chǔ)ppt課件.ppt

《算法效率分析基礎(chǔ)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第2章算法效率分析基礎(chǔ)一個問題往往有多個算法應(yīng)當(dāng)分析算法的品性怎樣評價一個算法？1一個算法好不好體現(xiàn)在運行該算法所需要的計算機(jī)資源的多少上所需資源越少，該算法越好；計算機(jī)最重要的資源是時間和空間算法分析對算法利用這兩種資源的效率做研究時間效率：指出正在討論的算法運行得有多快；空間效率：關(guān)心算法需要的額外空間。研究實驗告訴我們，對于大多數(shù)問題來說，我們在速度上能夠取得的進(jìn)展要遠(yuǎn)大于在空間上的進(jìn)展，所以我們把主要精力集中在時間效率上。22.1分析框架如何評價時間效率？2.1.1輸入規(guī)模的度量一個事實：問題規(guī)模越大，算法運行時間越長。將算

2、法輸入規(guī)模n為時間效率的參數(shù)。選擇哪個（些）參數(shù)作為輸入規(guī)模？32.1.2運行時間的度量單位可以采用秒，分，小時嗎？可以統(tǒng)計算法每一步的操作次數(shù)嗎？一般的做法：把基本操作（最重要的操作）次數(shù)作為算法運行時間的度量單位。思考下面算法的重要操作：排序矩陣乘法4建立一個算法時間效率的分析框架對于輸入規(guī)模為n的算法統(tǒng)計基本操作執(zhí)行次數(shù)C(n)，來對其效率進(jìn)行度量。在某個特定計算機(jī)上的某個算法程序的運行時間T(n)≈copC(n)基本操作的執(zhí)行時間基本操作次數(shù)5對下面的三個時間效率函數(shù)表達(dá)式,哪一個效率高?C1(n)=nC2(n)=n3C3(

3、n)=10nn=11110n=228100n=33271000n=非常大結(jié)論：1隨n的遞增，不同函數(shù)增幅不同2某些函數(shù)在大規(guī)模時增幅顯著，函數(shù)可以表示增幅的特點3我們希望選擇大規(guī)模時，時間效率增幅小的算法62.1.3增長次數(shù)（增長幅度）特別考慮大規(guī)模的輸入要強(qiáng)調(diào)執(zhí)行次數(shù)的增長次數(shù)呢？這是因為小規(guī)模輸入在運行時間上差別不足以將高效的算法和低效的算法法區(qū)分開來。7圖1－2各種函數(shù)的曲線8C(n)可以合理的度量算法的效率，但對同一個算法相同的規(guī)模下運行時間就一樣嗎？考慮順序查找：SequentialSearch(A[0..n-1],K)/

4、/輸入：數(shù)組A[0..n-1],和查找關(guān)鍵字K//輸出：返回第一個匹配K的元素下標(biāo)//如果沒有匹配的，返回-1i=0WhileiKdoi=i+1Ifi

5、在最優(yōu)情況下的效率。這時，與其它規(guī)模為n的輸入相比，該算法運行得最快。然而，無論是最差效率分析還是最優(yōu)效率分析都不能提供一種必要的信息：在“典型”或者“隨機(jī)”輸入的情況下，一個算法會具有什么樣的行為。這正是平均效率試圖提供給我們信息。112.1.5分析框架概要算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)行度量。我們用算法基本操作的執(zhí)行次數(shù)來度量算時間效率。通過計算算法消耗的額外存儲單元的數(shù)量來度量空間效率。在輸入規(guī)模相同的情況下，有些算法的效率會的顯著差異。對于這樣的算法，我們需要區(qū)分最差效率，平均效率和最優(yōu)效率。本框架主要關(guān)心，當(dāng)

6、算法的輸入規(guī)模趨向于無限大的時候，其運行時間（消耗的額外空間）函數(shù)的增長次數(shù)。122.2漸進(jìn)符號和基本效率類型2.2.1非正式的介紹非正式來說，O(g(n))是增長次數(shù)小于等于g(n)(以及其常數(shù)倍，n趨向于無窮大)的函數(shù)集合?？紤]O(n2)n∈O(n2),100n+5∈O(n2),1/2(n(n-1))∈O(n2),n3不屬于O(n2),13第二個符號?(g(n))，代表增長次數(shù)大于等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。n3∈?(n2)，1/2(n(n-1))∈?(n2)，但是100n+5∈?(n2)14最后，Θ

7、(g(n))是增長次數(shù)等于g(n)(以及其常數(shù)倍,n趨向于無窮大)的函數(shù)集合。例：每一個二次方程an2+bn+c在a>0的情況下都包含在Θ(n2)中。152.2.2符號О定義1把函數(shù)t(n)包含在O(g(n))中記作t(n)∈O(g(n))。稱t(n)的階不高于g(n)的階.成立條件：對于所有足夠大的n，t(n)的上界由g(n)的常數(shù)倍數(shù)所確定。即，存在大于0的常數(shù)c和非負(fù)的整數(shù)n0，使得：對于所有的n≥n0來說，t(n)≤cg(n)n0之前的情況無關(guān)重要,為什么？cg(n)t(n)n符號O：t(n)∈O(g(n))n0常用函數(shù)符號

8、：t(n)一個算法運行的時間函數(shù)C(n)基本操作次數(shù)函數(shù)g(n)用來比較的函數(shù)16t(n)=3n+2。說明屬于O(n)當(dāng)n≥n0=2時，3n+2≤3n+n＝4n此時c=4,g(n)=n。（向定義式靠攏）t(n)≤4g(n)t(n)∈O