算法設(shè)計(jì)與分析《算法設(shè)計(jì)與分析》1-漸近時(shí)間復(fù)雜度課件

《算法設(shè)計(jì)與分析》算法分析基礎(chǔ)-漸近時(shí)間復(fù)雜度信息管理學(xué)院

李季《算法設(shè)計(jì)與分析》算法分析基礎(chǔ)-漸近時(shí)間復(fù)雜度信息管理學(xué)院 內(nèi)容提要2022/11/25算法設(shè)計(jì)與分析2算法分析基礎(chǔ)P與NP問(wèn)題基礎(chǔ)遞歸分治動(dòng)態(tài)規(guī)劃貪心回溯分支限界算法設(shè)計(jì)經(jīng)典策略分析手段漸近分析與關(guān)鍵操作分析結(jié)果的表示漸近表示法與漸近時(shí)間復(fù)雜度練習(xí)內(nèi)容提要2022/11/22算法設(shè)計(jì)與分析2算法分析基礎(chǔ)P與算法與算法問(wèn)題2022/11/25算法設(shè)計(jì)與分析3問(wèn)題編程實(shí)現(xiàn)理解問(wèn)題數(shù)學(xué)建模確認(rèn)算法正確性證明分析算法時(shí)間復(fù)雜度空間復(fù)雜度策略選擇確定數(shù)據(jù)結(jié)構(gòu)確定過(guò)程結(jié)構(gòu)設(shè)計(jì)算法表示算法算法問(wèn)題求解框架算法與算法問(wèn)題2022/11/22算法設(shè)計(jì)與分析3問(wèn)題編程實(shí)漸近表示符號(hào)：大O記號(hào)、記號(hào)、記號(hào)、小o記號(hào)漸近表示法（漸近時(shí)間復(fù)雜度）：指出時(shí)間函數(shù)T的漸近上界或下界2022/11/25算法設(shè)計(jì)與分析4漸近時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度定義程序步計(jì)數(shù)關(guān)鍵操作計(jì)數(shù)T(n)漸近分析漸近時(shí)間復(fù)雜度如何區(qū)分算法運(yùn)行時(shí)間在增長(zhǎng)趨勢(shì)上的差異？T1(n)算法AT2(n)

算法Bn0n∞2022/11/22算法設(shè)計(jì)與分析4漸近時(shí)間復(fù)雜度算法時(shí)間復(fù)漸近表示法——度量函數(shù)的增長(zhǎng)趨勢(shì)2022/11/25算法設(shè)計(jì)與分析5分析結(jié)果的表示_漸近時(shí)間復(fù)雜度圖示定義意義f(n)=O(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：

f(n)≤cg(n)f(n)在數(shù)量級(jí)上小于等于g(n)或稱g(n)是一個(gè)上界f(n)=(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：

f(n)≥cg(n)f(n)在數(shù)量級(jí)上大于等于g(n)或稱g(n)是一個(gè)下界f(n)=(g(n))能找到c1,c2和n0,使當(dāng)n≥n0時(shí),總有:

c1g(n)≤f(n)≤c2g(n)f(n)在數(shù)量級(jí)上等于g(n)或稱f,g同階f(n)=o(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：f(n)<cg(n)f(n)在數(shù)量級(jí)上嚴(yán)格小于g(n)或稱f比g低階f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)f(n)cg(n)n0f(n)cg(n)n0c1g(n)c2g(n)f(n)n0f(n)cg(n)n0漸近表示法——度量函數(shù)的增長(zhǎng)趨勢(shì)2022/11/22算法設(shè)計(jì)例：f(n)=10n2+4n+2有f(n)=O(n2)因?yàn)椋寒?dāng)n≥5后，f(n)≤10n2+5n≤10n2+n2

≤11n2有f(n)=O(n3)因?yàn)椋寒?dāng)n≥11后，f(n)≤11n2≤n3有f(n)=(n2)因?yàn)椋寒?dāng)n≥1后，f(n)≥

10n2由1和2知，f有多個(gè)漸近上界，越逼近(緊)的上界對(duì)f的刻畫越精確由1和3知，f(n)=(n2)，即f和g=n2同階因?yàn)椋寒?dāng)n≥5后，10n2

≤f(n)≤11n22022/11/25算法設(shè)計(jì)與分析6漸近表示法應(yīng)用例：f(n)=10n2+4n+22022/11/算法設(shè)計(jì)關(guān)鍵操作計(jì)數(shù)(最壞情況下)T(n)漸近分析2022/11/25算法設(shè)計(jì)與分析7漸近表示法應(yīng)用//素?cái)?shù)判定算法1intIs_sushu(intN){inti;intflag=1;if(N==1)returnfalse;if(N==2)returntrue;for(i=2;i<=N;i++){if(N%i==0){flag=0;break;}}returnflag;}主要部分//素?cái)?shù)判定算法2intIs_sushu(intN){inti;intflag=1;if(N==1)returnfalse;if(N==2)returntrue;for(i=2;i<=sqrt(N);i++){if(N%i==0){flag=0;break;}}returnflag;}主要部分最壞時(shí)：T1=N關(guān)鍵操作執(zhí)行次數(shù)？關(guān)鍵操作執(zhí)行次數(shù)？最壞時(shí)：T2=sqrt(N)算法1和2的漸近特性有明顯的差異算法設(shè)計(jì)關(guān)鍵操作計(jì)數(shù)(最壞情況下)T(n)漸近分析2漸近時(shí)間復(fù)雜度（asymptoticcomplexity）這種使用記號(hào)大O///小o來(lái)漸近表示的算法時(shí)間漸近分析中參考函數(shù)g(n)：度量時(shí)間T漸近數(shù)量級(jí)常見(jiàn)函數(shù)如下:

分析結(jié)果的表示_漸近時(shí)間復(fù)雜度函數(shù)測(cè)試數(shù)量級(jí)g(n)=1常數(shù)級(jí)g(n)=logn對(duì)數(shù)級(jí)g(n)=nlogn線性對(duì)數(shù)級(jí)g(n)=n線性級(jí)g(n)=n2平方級(jí)g(n)=n3立方級(jí)g(n)=2n指數(shù)級(jí)多項(xiàng)式級(jí)別

及以下指數(shù)級(jí)別漸近時(shí)間復(fù)雜度（asymptoticcomplexity）為什么說(shuō)：速度為算法之魂給定條件：給定機(jī)器A、機(jī)器B和限定時(shí)間B的運(yùn)算速度是A的100倍給定時(shí)間內(nèi)機(jī)器的關(guān)鍵操作執(zhí)行能力(運(yùn)算量)不變對(duì)同一問(wèn)題有幾種不同級(jí)別的算法存在：O(n),O(n2),O(2n)計(jì)算量相同時(shí)，不同算法能解決的問(wèn)題規(guī)模n如下圖所示2022/11/25算法設(shè)計(jì)與分析9速度為算法之魂T(n)計(jì)算量(A)n算法110n10,0001000算法2n210,000100算法32n10,00013計(jì)算量(B)n’1,000,0001000001,000,00010001,000,00019規(guī)模變化n’/n100101.46要更快的算法勝于要更快的計(jì)算機(jī)為什么說(shuō)：速度為算法之魂2022/11/22算法設(shè)計(jì)與分析9求算法漸近時(shí)間復(fù)雜度的步驟：綜合示例：求直接插入排序算法時(shí)間復(fù)雜度設(shè)對(duì)表R中元素進(jìn)行升序排列，R中元素個(gè)數(shù)為n2022/11/25算法設(shè)計(jì)與分析10漸近分析小結(jié)分析情況：最好、最壞或平均關(guān)鍵操作計(jì)數(shù)求和漸近分析算法A分析關(guān)鍵操作漸近時(shí)間復(fù)雜度求算法漸近時(shí)間復(fù)雜度的步驟：2022/11/22算法設(shè)計(jì)與分voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

2022/11/25算法設(shè)計(jì)與分析11直接插入排序算法n-1趟插入關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較關(guān)鍵操作—移動(dòng)主要部分關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較分析關(guān)鍵操作voidlnsertSort(SeqListR)2022022/11/25算法設(shè)計(jì)與分析12直接插入排序算法voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

分析特殊情況關(guān)鍵操作—比較最好情況：R正序主要部分只有1個(gè)關(guān)鍵操作被執(zhí)行2022/11/22算法設(shè)計(jì)與分析12直接插入排序算法voi2022/11/25算法設(shè)計(jì)與分析13直接插入排序算法voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

分析特殊情況最壞情況：R反序關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較主要部分關(guān)鍵操作—移動(dòng)關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較所有關(guān)鍵操作被執(zhí)行，第2層循環(huán)內(nèi)的執(zhí)行次數(shù)最高2022/11/22算法設(shè)計(jì)與分析13直接插入排序算法voiR初始排列狀態(tài)最好情況(正序)

最壞情況(反序)無(wú)序(平均)第i趟元素比較次數(shù)1i+1(i-2)/2元素總比較次數(shù)n-1(n+2)(n-1)/2≈n*n/4第i趟元素移動(dòng)次數(shù)0i+2(i-2)/2元素總移動(dòng)次數(shù)0(n-1)(n+4)/2≈n*n/42022/11/25算法設(shè)計(jì)與分析14直接插入排序算法關(guān)鍵操作計(jì)數(shù)和漸近分析時(shí)間復(fù)雜度0(n)O(n*n)O(n*n)漸近分析最好情況：T(n)=(n-1)+0=O(n)最壞情況：T(n)=(n+2)(n-1)/2+(n-1)(n+4)/2=n2+2n-3=O(n*n)平均情況：T(n)≈n*n/4+n*n/4≈n*n/2=O(n*n)R初始排列狀態(tài)最好情況(正序)最壞情況(反序)無(wú)序(平均)1.證明：

如果f(n)=amnm+am1nm1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=(nm)。2.求以下算法A的漸近時(shí)間復(fù)雜度

練習(xí)【算法A】

矩陣乘法A×B=C,A/B/C均為n階方陣{voidmsqure(inta,intb,int&c){for（i=0;i<n;i++）for（j=0;j<n;j++）{c[i][j]=0;for（k=0;k<n;k++）c[i][j]+=a[i][k]*b[k][j];}}1.證明：如果f(n)=amnm+am1nm1.解答,分開(kāi)證明f(n)=O(nm)和f(n)=(nm)即可先證f(n)=O(nm)。取n0=1，當(dāng)n≥n0時(shí)，有

f(n)=amnm+am1nm1++a1n+a0

|am|nm+|am1|nm1++|a1|n+|a0|

(|am|+|am1|/n++|a1|/nm1+|a0|/nm)nm

(|am|+|am1|++|a1|+|a0|)nm可取c=|am|+|am1|++|a1|+|a0|，得證。

練習(xí)解答1.解答,分開(kāi)證明f(n)=O(nm)和f(n)=1.解答(cont.)再證明f(n)=(nm)：f(n)=amnm+am1nm1++a1n+a0令q=max{am,|am1|，

|a1|，|a0|}f(n)=nm(am+am-1/n+…+a1/nm-1+a0/nm

)≥nm(am-|am1|/n-…-|a1|/nm-1-|a0|/nm

)≥nm(am-q/n-…-q/nm-1-q/nm

)

≥nm(am-q/n-…-q/n-q/n

)

≥nm(am-q*m/n)若(am-q*m/n)≥0，只需n≥q*m/am

可取c=am/2.則當(dāng)n>2qm/am

時(shí),

就有f(n)≥cnm得證。

練習(xí)解答1.解答(cont.)練習(xí)解答2.求以下算法A的漸近時(shí)間復(fù)雜度如上圖所示，求各關(guān)鍵操作執(zhí)行次數(shù)，注意循環(huán)嵌套T=n3+n2(n+1)+n2+n(n+1)+(n+1)=2n3+3n2+2n+1=(n3)

練習(xí)解答【算法A】

矩陣乘法A×B=C,A/B/C均為n階方陣{voidmsqure(inta,intb,int&c){for（i=0;i<n;i++）//n+1for（j=0;j<n;j++）{ //n(n+1)c[i][j]=0; //n2for（k=0;k<n;k++）//n2(n+1)c[i][j]+=a[i][k]*b[k][j]; //n3}}2.求以下算法A的漸近時(shí)間復(fù)雜度練習(xí)解答【算法A】矩大O記號(hào)如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≤cg(n)，則記f(n)=O(g(n))。

漸近表示法(補(bǔ)充)例如：f(n)=10n2+4n+2=O(n2)因?yàn)椋寒?dāng)n>5后，f(n)<=10n2+5n<=10n2+n2<=11n2例如：f(n)=0.5n+1=O(n)因?yàn)椋寒?dāng)n>1后，f(n)<=0.5n+n<=1.5n例如：f(n)=0.5n+1=O(n2)因?yàn)椋寒?dāng)n>1.5后，f(n)<1.5n<=n2

f(n)cg(n)n0f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)表明f可以有多個(gè)上界，越逼近的描述越精確表明f的增長(zhǎng)趨勢(shì)在數(shù)量級(jí)上不超過(guò)g，或稱g為f的一個(gè)漸近上界大O記號(hào)漸近表示法(補(bǔ)充)例如：f(n)=10n2記號(hào)定義如果存在兩個(gè)正常數(shù)

c和n0，使得當(dāng)n≥n0時(shí)，有f(n)≥c

g(n)，則記做f(n)=(g(n))例f(n)=10n2+4n+2=(n2)因?yàn)閚>=1時(shí)，總有f(n)>=10n2例f(n)=2n+3=(n)因?yàn)閚>=1時(shí)，總有f(n)>=2n

漸近表示法(補(bǔ)充)f(n)cg(n)n0f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)記號(hào)定義漸近表示法(補(bǔ)充)f(n)cg(n)n0f記號(hào)定義如果存在正常數(shù)c1，c2和n0，使得當(dāng)n≥n0時(shí)，有c1g(n)≤f(n)≤c2g(n)，則記做f(n)=(g(n))。例

f(n)=2n+3=(n)，即2n+3(n)例

f(n)=10n2+4n+2=(n2)

漸近表示法(補(bǔ)充)c1g(n)c2g(n)f(n)n0f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)記號(hào)定義漸近表示法(補(bǔ)充)c1g(n)

漸近表示法(補(bǔ)充)

根據(jù)大O的定義，容易證明以下運(yùn)算規(guī)則：

(1)O(f)+O(g)=O(max(f,g))(2)O(f+g)=O(f)+O(g)(3)O(fg)=O(f)O(g)(4)如果g=O(f)，則O(f)+O(g)=O(f)(5)O(Cf)=O(f)，其中C是一個(gè)正的常數(shù)(6)f=O(f)(1)和(2)表明：時(shí)間函數(shù)T的增長(zhǎng)趨勢(shì)主要由高階項(xiàng)決定(5)表明：時(shí)間函數(shù)T的增長(zhǎng)趨勢(shì)與高階項(xiàng)的系數(shù)無(wú)關(guān)f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)漸近表示法(補(bǔ)充)根據(jù)大O的定義，容易證明以下運(yùn)《算法設(shè)計(jì)與分析》算法分析基礎(chǔ)-漸近時(shí)間復(fù)雜度信息管理學(xué)院

李季《算法設(shè)計(jì)與分析》算法分析基礎(chǔ)-漸近時(shí)間復(fù)雜度信息管理學(xué)院 內(nèi)容提要2022/11/25算法設(shè)計(jì)與分析24算法分析基礎(chǔ)P與NP問(wèn)題基礎(chǔ)遞歸分治動(dòng)態(tài)規(guī)劃貪心回溯分支限界算法設(shè)計(jì)經(jīng)典策略分析手段漸近分析與關(guān)鍵操作分析結(jié)果的表示漸近表示法與漸近時(shí)間復(fù)雜度練習(xí)內(nèi)容提要2022/11/22算法設(shè)計(jì)與分析2算法分析基礎(chǔ)P與算法與算法問(wèn)題2022/11/25算法設(shè)計(jì)與分析25問(wèn)題編程實(shí)現(xiàn)理解問(wèn)題數(shù)學(xué)建模確認(rèn)算法正確性證明分析算法時(shí)間復(fù)雜度空間復(fù)雜度策略選擇確定數(shù)據(jù)結(jié)構(gòu)確定過(guò)程結(jié)構(gòu)設(shè)計(jì)算法表示算法算法問(wèn)題求解框架算法與算法問(wèn)題2022/11/22算法設(shè)計(jì)與分析3問(wèn)題編程實(shí)漸近表示符號(hào)：大O記號(hào)、記號(hào)、記號(hào)、小o記號(hào)漸近表示法（漸近時(shí)間復(fù)雜度）：指出時(shí)間函數(shù)T的漸近上界或下界2022/11/25算法設(shè)計(jì)與分析26漸近時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度定義程序步計(jì)數(shù)關(guān)鍵操作計(jì)數(shù)T(n)漸近分析漸近時(shí)間復(fù)雜度如何區(qū)分算法運(yùn)行時(shí)間在增長(zhǎng)趨勢(shì)上的差異？T1(n)算法AT2(n)

算法Bn0n∞2022/11/22算法設(shè)計(jì)與分析4漸近時(shí)間復(fù)雜度算法時(shí)間復(fù)漸近表示法——度量函數(shù)的增長(zhǎng)趨勢(shì)2022/11/25算法設(shè)計(jì)與分析27分析結(jié)果的表示_漸近時(shí)間復(fù)雜度圖示定義意義f(n)=O(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：

f(n)≤cg(n)f(n)在數(shù)量級(jí)上小于等于g(n)或稱g(n)是一個(gè)上界f(n)=(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：

f(n)≥cg(n)f(n)在數(shù)量級(jí)上大于等于g(n)或稱g(n)是一個(gè)下界f(n)=(g(n))能找到c1,c2和n0,使當(dāng)n≥n0時(shí),總有:

c1g(n)≤f(n)≤c2g(n)f(n)在數(shù)量級(jí)上等于g(n)或稱f,g同階f(n)=o(g(n))能找到c和n0,使得當(dāng)n≥n0時(shí)，總有：f(n)<cg(n)f(n)在數(shù)量級(jí)上嚴(yán)格小于g(n)或稱f比g低階f(n)和g(n)是定義在自然數(shù)集合上的正函數(shù)f(n)cg(n)n0f(n)cg(n)n0c1g(n)c2g(n)f(n)n0f(n)cg(n)n0漸近表示法——度量函數(shù)的增長(zhǎng)趨勢(shì)2022/11/22算法設(shè)計(jì)例：f(n)=10n2+4n+2有f(n)=O(n2)因?yàn)椋寒?dāng)n≥5后，f(n)≤10n2+5n≤10n2+n2

≤11n2有f(n)=O(n3)因?yàn)椋寒?dāng)n≥11后，f(n)≤11n2≤n3有f(n)=(n2)因?yàn)椋寒?dāng)n≥1后，f(n)≥

10n2由1和2知，f有多個(gè)漸近上界，越逼近(緊)的上界對(duì)f的刻畫越精確由1和3知，f(n)=(n2)，即f和g=n2同階因?yàn)椋寒?dāng)n≥5后，10n2

≤f(n)≤11n22022/11/25算法設(shè)計(jì)與分析28漸近表示法應(yīng)用例：f(n)=10n2+4n+22022/11/算法設(shè)計(jì)關(guān)鍵操作計(jì)數(shù)(最壞情況下)T(n)漸近分析2022/11/25算法設(shè)計(jì)與分析29漸近表示法應(yīng)用//素?cái)?shù)判定算法1intIs_sushu(intN){inti;intflag=1;if(N==1)returnfalse;if(N==2)returntrue;for(i=2;i<=N;i++){if(N%i==0){flag=0;break;}}returnflag;}主要部分//素?cái)?shù)判定算法2intIs_sushu(intN){inti;intflag=1;if(N==1)returnfalse;if(N==2)returntrue;for(i=2;i<=sqrt(N);i++){if(N%i==0){flag=0;break;}}returnflag;}主要部分最壞時(shí)：T1=N關(guān)鍵操作執(zhí)行次數(shù)？關(guān)鍵操作執(zhí)行次數(shù)？最壞時(shí)：T2=sqrt(N)算法1和2的漸近特性有明顯的差異算法設(shè)計(jì)關(guān)鍵操作計(jì)數(shù)(最壞情況下)T(n)漸近分析2漸近時(shí)間復(fù)雜度（asymptoticcomplexity）這種使用記號(hào)大O///小o來(lái)漸近表示的算法時(shí)間漸近分析中參考函數(shù)g(n)：度量時(shí)間T漸近數(shù)量級(jí)常見(jiàn)函數(shù)如下:

分析結(jié)果的表示_漸近時(shí)間復(fù)雜度函數(shù)測(cè)試數(shù)量級(jí)g(n)=1常數(shù)級(jí)g(n)=logn對(duì)數(shù)級(jí)g(n)=nlogn線性對(duì)數(shù)級(jí)g(n)=n線性級(jí)g(n)=n2平方級(jí)g(n)=n3立方級(jí)g(n)=2n指數(shù)級(jí)多項(xiàng)式級(jí)別

及以下指數(shù)級(jí)別漸近時(shí)間復(fù)雜度（asymptoticcomplexity）為什么說(shuō)：速度為算法之魂給定條件：給定機(jī)器A、機(jī)器B和限定時(shí)間B的運(yùn)算速度是A的100倍給定時(shí)間內(nèi)機(jī)器的關(guān)鍵操作執(zhí)行能力(運(yùn)算量)不變對(duì)同一問(wèn)題有幾種不同級(jí)別的算法存在：O(n),O(n2),O(2n)計(jì)算量相同時(shí)，不同算法能解決的問(wèn)題規(guī)模n如下圖所示2022/11/25算法設(shè)計(jì)與分析31速度為算法之魂T(n)計(jì)算量(A)n算法110n10,0001000算法2n210,000100算法32n10,00013計(jì)算量(B)n’1,000,0001000001,000,00010001,000,00019規(guī)模變化n’/n100101.46要更快的算法勝于要更快的計(jì)算機(jī)為什么說(shuō)：速度為算法之魂2022/11/22算法設(shè)計(jì)與分析9求算法漸近時(shí)間復(fù)雜度的步驟：綜合示例：求直接插入排序算法時(shí)間復(fù)雜度設(shè)對(duì)表R中元素進(jìn)行升序排列，R中元素個(gè)數(shù)為n2022/11/25算法設(shè)計(jì)與分析32漸近分析小結(jié)分析情況：最好、最壞或平均關(guān)鍵操作計(jì)數(shù)求和漸近分析算法A分析關(guān)鍵操作漸近時(shí)間復(fù)雜度求算法漸近時(shí)間復(fù)雜度的步驟：2022/11/22算法設(shè)計(jì)與分voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

2022/11/25算法設(shè)計(jì)與分析33直接插入排序算法n-1趟插入關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較關(guān)鍵操作—移動(dòng)主要部分關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較分析關(guān)鍵操作voidlnsertSort(SeqListR)2022022/11/25算法設(shè)計(jì)與分析34直接插入排序算法voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

分析特殊情況關(guān)鍵操作—比較最好情況：R正序主要部分只有1個(gè)關(guān)鍵操作被執(zhí)行2022/11/22算法設(shè)計(jì)與分析12直接插入排序算法voi2022/11/25算法設(shè)計(jì)與分析35直接插入排序算法voidlnsertSort(SeqListR){//對(duì)順序表R中的元素R[1..n]按升序進(jìn)行插入排序

inti，j；

for(i=2;i<=n；i++)//依次插入R[2]，…，R[n]

if(R[i]<R[i-1])

{//若R[i]>=有序區(qū)中元素，則R[i]不動(dòng)

R[0]=R[i];j=i-1;//R[0]是哨兵，且是R[i]的副本

do{//從右向左在有序區(qū)R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//將關(guān)鍵字大于R[i]的記錄后移

}while(R[0]<R[j])；//當(dāng)R[i]≥R[j]時(shí)終止

R[j+1]=R[0]；//R[i]插入到正確的位置上

}//endif}//InsertSort

分析特殊情況最壞情況：R反序關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較主要部分關(guān)鍵操作—移動(dòng)關(guān)鍵操作—移動(dòng)關(guān)鍵操作—比較所有關(guān)鍵操作被執(zhí)行，第2層循環(huán)內(nèi)的執(zhí)行次數(shù)最高2022/11/22算法設(shè)計(jì)與分析13直接插入排序算法voiR初始排列狀態(tài)最好情況(正序)

最壞情況(反序)無(wú)序(平均)第i趟元素比較次數(shù)1i+1(i-2)/2元素總比較次數(shù)n-1(n+2)(n-1)/2≈n*n/4第i趟元素移動(dòng)次數(shù)0i+2(i-2)/2元素總移動(dòng)次數(shù)0(n-1)(n+4)/2≈n*n/42022/11/25算法設(shè)計(jì)與分析36直接插入排序算法關(guān)鍵操作計(jì)數(shù)和漸近分析時(shí)間復(fù)雜度0(n)O(n*n)O(n*n)漸近分析最好情況：T(n)=(n-1)+0=O(n)最壞情況：T(n)=(n+2)(n-1)/2+(n-1)(n+4)/2=n2+2n-3=O(n*n)平均情況：T(n)≈n*n/4+n*n/4≈n*n/2=O(n*n)R初始排列狀態(tài)最好情況(正序)最壞情況(反序)無(wú)序(平均)1.證明：

如果f(n)=amnm+am1nm1+…+a1n+a0是m次多項(xiàng)式，且am＞0，則f(n)=(nm)。2.求以下算法A的漸近時(shí)間復(fù)雜度

練習(xí)【算法A】

矩陣乘法A×B=C,A/B/C均為n階方陣{voidmsqure(inta,intb,int&c){for（i=0;i<n;i++）for（j=0;j<n;j++）{c[i][j]=0;for（k=0;k<n;k++）c[i][j]+=a[i][k]*b[k][j];}}1.證明：如果f(n)=amnm+am1nm1.解答,分開(kāi)證明f(n)=O(nm)和f(n)=(nm)即可先證f(n)=O(nm)。取n0=1，當(dāng)n≥n0時(shí)，有

f(n)=amnm+am1nm1++a1n+a0

|am|nm+|am1|nm1++|a1|n+|a0|

(|am|+|am1|/n++|a1|/nm1+|a0|/nm)nm

(|am|+|am1|++|a1|+|a0|)nm可取c=|am|+|am1|++|a1|+|a0|，得證。

練習(xí)解答1.解答,分開(kāi)證明f(n)=O(nm)和f(n)=1.解答(cont.)再證明f(n)=(nm)：f(n)=amnm+am1nm1++a1n+a0令q=max{am,|am1|，

|a1|，|a0|}f(n)=nm(am+am-1/n+…+a1/nm-1+a0/nm

)≥nm(am-|am1|/n-…-|a1|/nm-1-|a0|/nm

)≥nm(am-q/n-…-q/nm-1-q/nm

)

≥nm(am-q/n-…-q/n-q/n

)

≥nm(am-q*m/n)若(am-q*m/n)≥0，只需n≥q*m/am

可取c=am/2.則當(dāng)n>2qm/am

時(shí),

就有f(n)≥cnm得證。

練習(xí)解答1.解答(cont.)練習(xí)解答2.求以下算法A的漸近時(shí)間復(fù)雜度如上圖所示，求各關(guān)鍵操作執(zhí)行次數(shù)，注意循環(huán)嵌套T=n3+n2(n+1)+n2+n(n+1)+(n+1)=2n3+3n2+2n+1=(n3)

練習(xí)解答【算法A】

矩陣乘法A×B=C,A/B/C均為