算法效率分析基礎第二章

算法效率分析基礎第二章算法分析與設計

AnalysisandDesignofComputerAlgorithms

第二章算法效率分析基礎算法效率分析基礎算法分析是對一個算法需要多少計算時間和存儲空間作定量的分析。TimeisImportant不是所有能計算的都有價值，不是所有有價值的都能被計算——阿爾伯特.愛因斯坦教學內(nèi)容算法效率分析框架算法效率的表示符號非遞歸算法的效率分析遞歸算法的效率分析算法的經(jīng)驗分析要求掌握算法中近似時間的表示、非遞歸、遞歸算法的效率分析方法，了解算法的經(jīng)驗分析分析框架——輸入規(guī)模度量輸入規(guī)模度量算法的時間效率和空間效率都用輸入規(guī)模的函數(shù)進行度量。對于所有的算法，對于規(guī)模更大的輸入都需要運行更長的時間。經(jīng)常使用一個輸入規(guī)模n為參數(shù)的函數(shù)來研究算法的效率。選擇輸入規(guī)模的合適量度，要受到所討論算法的操作細節(jié)影響。分析框架——運行時間的度量單位運行時間的度量單位用算法的基本操作（算法中最重要的操作）的執(zhí)行次數(shù)來度量算法的時間效率。基本操作通常是算法最內(nèi)層循環(huán)中最費時的操作。算法運行時間的估計：T(n)≈copC(n)n是該算法的輸入規(guī)模cop是特定計算機上一個算法基本操作的執(zhí)行時間C(n)是該算法需要執(zhí)行的基本操作的次數(shù)分析框架——增長次數(shù)增長次數(shù)小規(guī)模輸入在運行時間上的差別不足以將高效的算法和低效的算法區(qū)分開來。一個需要指數(shù)級操作次數(shù)的算法只能用來解決規(guī)模非常小的問題分析框架——算法的最優(yōu)、最差和平均效率算法的最優(yōu)、最差和平均效率最差效率是指在輸入規(guī)模為n時，算法在最壞情況下的效率。最優(yōu)效率是指在輸入規(guī)模為n是，算法在最優(yōu)情況下的效率。平均效率是指在“典型”或“隨機”輸入的情況下，算法具有的行為（效率）。攤銷效率是指對于同樣的數(shù)據(jù)結(jié)構(gòu)執(zhí)行多次操作，然后分攤到每一次上。漸進符號算法效率的主要指標是基本操作次數(shù)的增長次數(shù)。為了對這些增長次數(shù)進行比較和歸類，計算機科學家們使用了3種符號：O（讀“O”）：上界Ω（讀”omega”）：下界Θ（讀”theta”）：近似符號O定義1對于足夠大的n，t(n)的上界由g(n)的常數(shù)倍來確定，即：記為t(n)∈O(g(n))t(n)≤cg(n)，c為常數(shù)n∈O(n2)100n+5∈O(n2)n(n-1)/2∈O(n2)符號Ω定義2對于足夠大的n，t(n)的下界由g(n)的常數(shù)倍來確定，即：記為t(n)∈Ω(g(n))t(n)≥

cg(n)，c為常數(shù)n3∈Ω

(n2)n(n+1)∈Ω

(n2)4n2+5∈Ω(n2)符號Θ定義3對于足夠大的n，t(n)的上界和下界由g(n)的常數(shù)倍來確定，即：記為t(n)∈Θ(g(n))c2g(n)≤t(n)≤

c1g(n)，c1,c2為常數(shù)n2+3n+2∈Θ

(n2)n(n-1)/2∈Θ

(n2)4n2+5∈Θ(n2)漸進符號的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，則

t1(n)+t2(n)∈O(max{(g1(n),g2(n)})對于符號Ω和Θ，該定理也成立。該定理表明：當算法由兩個連續(xù)執(zhí)行部分組成時，該算法的整體效率由具有較大增長次數(shù)的那部分所決定。利用極限比較增長次數(shù)前兩種情況意味著t(n)∈O(g(n))后兩種情況意味著t(n)∈Ω(g(n))第二種情況意味著t(n)∈Θ(g(n))基本的效率類型常量(1)、對數(shù)(logn)、線性(n)、nlogn、平方(n2)、立方(n3)、指數(shù)(2n)、階乘(n!)非遞歸算法的數(shù)學分析Exle1：討論下面這個算法（從n個元素中查找最大元素問題）的效率。算法MaxElement(A[0..n-1]//求給定數(shù)組中的最大元素//輸入：實數(shù)數(shù)組A[0..n-1]//輸出：A中的最大元素maxvalA[0]fori1ton-1doifA[i]>maxvalmaxvalA[i]returnmaxval考慮：循環(huán)中的操作有比較和賦值，取哪一個作為基本操作？輸入規(guī)模是多少？基本操作為：比較運算輸入規(guī)模就是數(shù)組長度n算法的效率為：分析非遞歸算法效率的通用方案決定用那些參數(shù)作為輸入規(guī)模的度量。找出算法的基本操作。檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。建立一個算法基本操作執(zhí)行次數(shù)的求和表達式。利用求和運算的標準公式和法則來建立一個操作次數(shù)的閉合公式，或者至少確定它的增長次數(shù)。Exle考慮下面算法的效率Exle2元素唯一性問題算法UniqueElements(A[0..n-1])//驗證給定數(shù)組的元素是否全部唯一//輸入：實數(shù)數(shù)組A[0..n-1]//輸出：如果唯一，返回True，否則Falsefori0ton-2doforji+1ton-1doifA[i]=A[j]returnFalsereturnTrueExle3兩個n階方陣乘法算法MatrixMuti(A[0..n-1,0..n-1],B[0..n-1,0..n-1])//根據(jù)定義計算兩個n階矩陣的乘積//輸入：兩個n階矩陣//輸出：矩陣C=ABfori0ton-1doforj0ton-1doC[i,j]0.0fork0ton-1doC[i,j]=C[i,j]+A[i,k]*B[k,j]returnC遞歸算法的數(shù)學分析例：對于任意非負整數(shù)n，計算F(n)=n!的值。F(n)=n(n-1)!,n>11,n=11,n=0算法F(n)//遞歸計算n!//輸入：非負整數(shù)n//輸出：n!的值ifn=0retuen1elsereturnF(n-1)*nM(n)=M(n-1)+1,n≥10,n=0M(n)=M(n-1)+1=[M(n-2)+1]+1=M(n-2)+2=[M(n-3)+1]+2=M(n-3)+3……=[M(n-n)+1]+n-1=n分析遞歸算法效率的通用方案決定用哪個參數(shù)作為輸入規(guī)模的度量找出算法的基本操作檢查對相同規(guī)模的輸入，基本操作的執(zhí)行次數(shù)是否相同，如果不同，必須對最差、平均及最優(yōu)效率單獨研究建立一個遞推關系式及相應的初始條件求解這個遞歸關系式，或者至少確定解的增長次數(shù)漢諾塔M(n)=2M(n-1)+1,n>11,n=1M(n)=2n-1我們應該謹慎使用遞歸算法，因為他們的簡潔可能會掩蓋他們的低效率。斐波那契數(shù)列F(n)=F(n-1)+F(n-2),n>11,n=10,n=00,1,1,2,3,5,8,13,21,34,……算法的經(jīng)驗分析對算法效率做經(jīng)驗分析的通用方案了解試驗的目的決定用來度量效率的量度M和度量單位（單位時間內(nèi)的操作次數(shù)）決定輸入樣本的特性為實驗準備算法的程序?qū)崿F(xiàn)生成輸入樣本對輸入樣本進行計算，并記錄觀察到的實驗數(shù)據(jù)分析獲得的實驗數(shù)據(jù)算法可視法通過使用圖形來傳達關于算法的一些有用信息。算法可視法的種類：靜態(tài)算法可視法動態(tài)算法可視法(算法動畫,AlgorithmAnimation)靜