算法效率分析基礎(chǔ)第二章

算法效率分析基礎(chǔ)第二章算法分析與設(shè)計(jì)

AnalysisandDesignofComputerAlgorithms

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

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

(n2)n(n+1)∈Ω

(n2)4n2+5∈Ω(n2)符號(hào)Θ定義3對(duì)于足夠大的n，t(n)的上界和下界由g(n)的常數(shù)倍來(lái)確定，即：記為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)漸進(jìn)符號(hào)的有用特性定理如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，則

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