算法设计与分析《算法设计与分析》1-渐近时间复杂度课件

《算法设计与分析》算法分析基础-渐近时间复杂度信息管理学院

李季《算法设计与分析》算法分析基础-渐近时间复杂度信息管理学院 内容提要2022/11/25算法设计与分析2算法分析基础P与NP问题基础递归分治动态规划贪心回溯分支限界算法设计经典策略分析手段渐近分析与关键操作分析结果的表示渐近表示法与渐近时间复杂度练习内容提要2022/11/22算法设计与分析2算法分析基础P与算法与算法问题2022/11/25算法设计与分析3问题编程实现理解问题数学建模确认算法正确性证明分析算法时间复杂度空间复杂度策略选择确定数据结构确定过程结构设计算法表示算法算法问题求解框架算法与算法问题2022/11/22算法设计与分析3问题编程实渐近表示符号：大O记号、记号、记号、小o记号渐近表示法（渐近时间复杂度）：指出时间函数T的渐近上界或下界2022/11/25算法设计与分析4渐近时间复杂度算法时间复杂度定义程序步计数关键操作计数T(n)渐近分析渐近时间复杂度如何区分算法运行时间在增长趋势上的差异？T1(n)算法AT2(n)

算法Bn0n∞2022/11/22算法设计与分析4渐近时间复杂度算法时间复渐近表示法——度量函数的增长趋势2022/11/25算法设计与分析5分析结果的表示_渐近时间复杂度图示定义意义f(n)=O(g(n))能找到c和n0,使得当n≥n0时，总有：

f(n)≤cg(n)f(n)在数量级上小于等于g(n)或称g(n)是一个上界f(n)=(g(n))能找到c和n0,使得当n≥n0时，总有：

f(n)≥cg(n)f(n)在数量级上大于等于g(n)或称g(n)是一个下界f(n)=(g(n))能找到c1,c2和n0,使当n≥n0时,总有:

c1g(n)≤f(n)≤c2g(n)f(n)在数量级上等于g(n)或称f,g同阶f(n)=o(g(n))能找到c和n0,使得当n≥n0时，总有：f(n)<cg(n)f(n)在数量级上严格小于g(n)或称f比g低阶f(n)和g(n)是定义在自然数集合上的正函数f(n)cg(n)n0f(n)cg(n)n0c1g(n)c2g(n)f(n)n0f(n)cg(n)n0渐近表示法——度量函数的增长趋势2022/11/22算法设计例：f(n)=10n2+4n+2有f(n)=O(n2)因为：当n≥5后，f(n)≤10n2+5n≤10n2+n2

≤11n2有f(n)=O(n3)因为：当n≥11后，f(n)≤11n2≤n3有f(n)=(n2)因为：当n≥1后，f(n)≥

10n2由1和2知，f有多个渐近上界，越逼近(紧)的上界对f的刻画越精确由1和3知，f(n)=(n2)，即f和g=n2同阶因为：当n≥5后，10n2

≤f(n)≤11n22022/11/25算法设计与分析6渐近表示法应用例：f(n)=10n2+4n+22022/11/算法设计关键操作计数(最坏情况下)T(n)渐近分析2022/11/25算法设计与分析7渐近表示法应用//素数判定算法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;}主要部分//素数判定算法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;}主要部分最坏时：T1=N关键操作执行次数？关键操作执行次数？最坏时：T2=sqrt(N)算法1和2的渐近特性有明显的差异算法设计关键操作计数(最坏情况下)T(n)渐近分析2渐近时间复杂度（asymptoticcomplexity）这种使用记号大O///小o来渐近表示的算法时间渐近分析中参考函数g(n)：度量时间T渐近数量级常见函数如下:

分析结果的表示_渐近时间复杂度函数测试数量级g(n)=1常数级g(n)=logn对数级g(n)=nlogn线性对数级g(n)=n线性级g(n)=n2平方级g(n)=n3立方级g(n)=2n指数级多项式级别

及以下指数级别渐近时间复杂度（asymptoticcomplexity）为什么说：速度为算法之魂给定条件：给定机器A、机器B和限定时间B的运算速度是A的100倍给定时间内机器的关键操作执行能力(运算量)不变对同一问题有几种不同级别的算法存在：O(n),O(n2),O(2n)计算量相同时，不同算法能解决的问题规模n如下图所示2022/11/25算法设计与分析9速度为算法之魂T(n)计算量(A)n算法110n10,0001000算法2n210,000100算法32n10,00013计算量(B)n’1,000,0001000001,000,00010001,000,00019规模变化n’/n100101.46要更快的算法胜于要更快的计算机为什么说：速度为算法之魂2022/11/22算法设计与分析9求算法渐近时间复杂度的步骤：综合示例：求直接插入排序算法时间复杂度设对表R中元素进行升序排列，R中元素个数为n2022/11/25算法设计与分析10渐近分析小结分析情况：最好、最坏或平均关键操作计数求和渐近分析算法A分析关键操作渐近时间复杂度求算法渐近时间复杂度的步骤：2022/11/22算法设计与分voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

2022/11/25算法设计与分析11直接插入排序算法n-1趟插入关键操作—移动关键操作—比较关键操作—移动主要部分关键操作—移动关键操作—比较分析关键操作voidlnsertSort(SeqListR)2022022/11/25算法设计与分析12直接插入排序算法voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

分析特殊情况关键操作—比较最好情况：R正序主要部分只有1个关键操作被执行2022/11/22算法设计与分析12直接插入排序算法voi2022/11/25算法设计与分析13直接插入排序算法voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

分析特殊情况最坏情况：R反序关键操作—移动关键操作—比较主要部分关键操作—移动关键操作—移动关键操作—比较所有关键操作被执行，第2层循环内的执行次数最高2022/11/22算法设计与分析13直接插入排序算法voiR初始排列状态最好情况(正序)

最坏情况(反序)无序(平均)第i趟元素比较次数1i+1(i-2)/2元素总比较次数n-1(n+2)(n-1)/2≈n*n/4第i趟元素移动次数0i+2(i-2)/2元素总移动次数0(n-1)(n+4)/2≈n*n/42022/11/25算法设计与分析14直接插入排序算法关键操作计数和渐近分析时间复杂度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初始排列状态最好情况(正序)最坏情况(反序)无序(平均)1.证明：

如果f(n)=amnm+am1nm1+…+a1n+a0是m次多项式，且am＞0，则f(n)=(nm)。2.求以下算法A的渐近时间复杂度

练习【算法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.解答,分开证明f(n)=O(nm)和f(n)=(nm)即可先证f(n)=O(nm)。取n0=1，当n≥n0时，有

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|，得证。

练习解答1.解答,分开证明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.则当n>2qm/am

时,

就有f(n)≥cnm得证。

练习解答1.解答(cont.)练习解答2.求以下算法A的渐近时间复杂度如上图所示，求各关键操作执行次数，注意循环嵌套T=n3+n2(n+1)+n2+n(n+1)+(n+1)=2n3+3n2+2n+1=(n3)

练习解答【算法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的渐近时间复杂度练习解答【算法A】矩大O记号如果存在两个正常数c和n0，使得当n≥n0时，有f(n)≤cg(n)，则记f(n)=O(g(n))。

渐近表示法(补充)例如：f(n)=10n2+4n+2=O(n2)因为：当n>5后，f(n)<=10n2+5n<=10n2+n2<=11n2例如：f(n)=0.5n+1=O(n)因为：当n>1后，f(n)<=0.5n+n<=1.5n例如：f(n)=0.5n+1=O(n2)因为：当n>1.5后，f(n)<1.5n<=n2

f(n)cg(n)n0f(n)和g(n)是定义在自然数集合上的正函数表明f可以有多个上界，越逼近的描述越精确表明f的增长趋势在数量级上不超过g，或称g为f的一个渐近上界大O记号渐近表示法(补充)例如：f(n)=10n2记号定义如果存在两个正常数

c和n0，使得当n≥n0时，有f(n)≥c

g(n)，则记做f(n)=(g(n))例f(n)=10n2+4n+2=(n2)因为n>=1时，总有f(n)>=10n2例f(n)=2n+3=(n)因为n>=1时，总有f(n)>=2n

渐近表示法(补充)f(n)cg(n)n0f(n)和g(n)是定义在自然数集合上的正函数记号定义渐近表示法(补充)f(n)cg(n)n0f记号定义如果存在正常数c1，c2和n0，使得当n≥n0时，有c1g(n)≤f(n)≤c2g(n)，则记做f(n)=(g(n))。例

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

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

渐近表示法(补充)c1g(n)c2g(n)f(n)n0f(n)和g(n)是定义在自然数集合上的正函数记号定义渐近表示法(补充)c1g(n)

渐近表示法(补充)

根据大O的定义，容易证明以下运算规则：

(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是一个正的常数(6)f=O(f)(1)和(2)表明：时间函数T的增长趋势主要由高阶项决定(5)表明：时间函数T的增长趋势与高阶项的系数无关f(n)和g(n)是定义在自然数集合上的正函数渐近表示法(补充)根据大O的定义，容易证明以下运《算法设计与分析》算法分析基础-渐近时间复杂度信息管理学院

李季《算法设计与分析》算法分析基础-渐近时间复杂度信息管理学院 内容提要2022/11/25算法设计与分析24算法分析基础P与NP问题基础递归分治动态规划贪心回溯分支限界算法设计经典策略分析手段渐近分析与关键操作分析结果的表示渐近表示法与渐近时间复杂度练习内容提要2022/11/22算法设计与分析2算法分析基础P与算法与算法问题2022/11/25算法设计与分析25问题编程实现理解问题数学建模确认算法正确性证明分析算法时间复杂度空间复杂度策略选择确定数据结构确定过程结构设计算法表示算法算法问题求解框架算法与算法问题2022/11/22算法设计与分析3问题编程实渐近表示符号：大O记号、记号、记号、小o记号渐近表示法（渐近时间复杂度）：指出时间函数T的渐近上界或下界2022/11/25算法设计与分析26渐近时间复杂度算法时间复杂度定义程序步计数关键操作计数T(n)渐近分析渐近时间复杂度如何区分算法运行时间在增长趋势上的差异？T1(n)算法AT2(n)

算法Bn0n∞2022/11/22算法设计与分析4渐近时间复杂度算法时间复渐近表示法——度量函数的增长趋势2022/11/25算法设计与分析27分析结果的表示_渐近时间复杂度图示定义意义f(n)=O(g(n))能找到c和n0,使得当n≥n0时，总有：

f(n)≤cg(n)f(n)在数量级上小于等于g(n)或称g(n)是一个上界f(n)=(g(n))能找到c和n0,使得当n≥n0时，总有：

f(n)≥cg(n)f(n)在数量级上大于等于g(n)或称g(n)是一个下界f(n)=(g(n))能找到c1,c2和n0,使当n≥n0时,总有:

c1g(n)≤f(n)≤c2g(n)f(n)在数量级上等于g(n)或称f,g同阶f(n)=o(g(n))能找到c和n0,使得当n≥n0时，总有：f(n)<cg(n)f(n)在数量级上严格小于g(n)或称f比g低阶f(n)和g(n)是定义在自然数集合上的正函数f(n)cg(n)n0f(n)cg(n)n0c1g(n)c2g(n)f(n)n0f(n)cg(n)n0渐近表示法——度量函数的增长趋势2022/11/22算法设计例：f(n)=10n2+4n+2有f(n)=O(n2)因为：当n≥5后，f(n)≤10n2+5n≤10n2+n2

≤11n2有f(n)=O(n3)因为：当n≥11后，f(n)≤11n2≤n3有f(n)=(n2)因为：当n≥1后，f(n)≥

10n2由1和2知，f有多个渐近上界，越逼近(紧)的上界对f的刻画越精确由1和3知，f(n)=(n2)，即f和g=n2同阶因为：当n≥5后，10n2

≤f(n)≤11n22022/11/25算法设计与分析28渐近表示法应用例：f(n)=10n2+4n+22022/11/算法设计关键操作计数(最坏情况下)T(n)渐近分析2022/11/25算法设计与分析29渐近表示法应用//素数判定算法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;}主要部分//素数判定算法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;}主要部分最坏时：T1=N关键操作执行次数？关键操作执行次数？最坏时：T2=sqrt(N)算法1和2的渐近特性有明显的差异算法设计关键操作计数(最坏情况下)T(n)渐近分析2渐近时间复杂度（asymptoticcomplexity）这种使用记号大O///小o来渐近表示的算法时间渐近分析中参考函数g(n)：度量时间T渐近数量级常见函数如下:

分析结果的表示_渐近时间复杂度函数测试数量级g(n)=1常数级g(n)=logn对数级g(n)=nlogn线性对数级g(n)=n线性级g(n)=n2平方级g(n)=n3立方级g(n)=2n指数级多项式级别

及以下指数级别渐近时间复杂度（asymptoticcomplexity）为什么说：速度为算法之魂给定条件：给定机器A、机器B和限定时间B的运算速度是A的100倍给定时间内机器的关键操作执行能力(运算量)不变对同一问题有几种不同级别的算法存在：O(n),O(n2),O(2n)计算量相同时，不同算法能解决的问题规模n如下图所示2022/11/25算法设计与分析31速度为算法之魂T(n)计算量(A)n算法110n10,0001000算法2n210,000100算法32n10,00013计算量(B)n’1,000,0001000001,000,00010001,000,00019规模变化n’/n100101.46要更快的算法胜于要更快的计算机为什么说：速度为算法之魂2022/11/22算法设计与分析9求算法渐近时间复杂度的步骤：综合示例：求直接插入排序算法时间复杂度设对表R中元素进行升序排列，R中元素个数为n2022/11/25算法设计与分析32渐近分析小结分析情况：最好、最坏或平均关键操作计数求和渐近分析算法A分析关键操作渐近时间复杂度求算法渐近时间复杂度的步骤：2022/11/22算法设计与分voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

2022/11/25算法设计与分析33直接插入排序算法n-1趟插入关键操作—移动关键操作—比较关键操作—移动主要部分关键操作—移动关键操作—比较分析关键操作voidlnsertSort(SeqListR)2022022/11/25算法设计与分析34直接插入排序算法voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

分析特殊情况关键操作—比较最好情况：R正序主要部分只有1个关键操作被执行2022/11/22算法设计与分析12直接插入排序算法voi2022/11/25算法设计与分析35直接插入排序算法voidlnsertSort(SeqListR){//对顺序表R中的元素R[1..n]按升序进行插入排序

inti，j；

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

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

{//若R[i]>=有序区中元素，则R[i]不动

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

do{//从右向左在有序区R[1．．i-1]中查找R[i]的插入位置

R[j+1]=R[j]；j--；//将关键字大于R[i]的记录后移

}while(R[0]<R[j])；//当R[i]≥R[j]时终止

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

}//endif}//InsertSort

分析特殊情况最坏情况：R反序关键操作—移动关键操作—比较主要部分关键操作—移动关键操作—移动关键操作—比较所有关键操作被执行，第2层循环内的执行次数最高2022/11/22算法设计与分析13直接插入排序算法voiR初始排列状态最好情况(正序)

最坏情况(反序)无序(平均)第i趟元素比较次数1i+1(i-2)/2元素总比较次数n-1(n+2)(n-1)/2≈n*n/4第i趟元素移动次数0i+2(i-2)/2元素总移动次数0(n-1)(n+4)/2≈n*n/42022/11/25算法设计与分析36直接插入排序算法关键操作计数和渐近分析时间复杂度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初始排列状态最好情况(正序)最坏情况(反序)无序(平均)1.证明：

如果f(n)=amnm+am1nm1+…+a1n+a0是m次多项式，且am＞0，则f(n)=(nm)。2.求以下算法A的渐近时间复杂度

练习【算法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.解答,分开证明f(n)=O(nm)和f(n)=(nm)即可先证f(n)=O(nm)。取n0=1，当n≥n0时，有

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|，得证。

练习解答1.解答,分开证明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.则当n>2qm/am

时,

就有f(n)≥cnm得证。

练习解答1.解答(cont.)练习解答2.求以下算法A的渐近时间复杂度如上图所示，求各关键操作执行次数，注意循环嵌套T=n3+n2(n+1)+n2+n(n+1)+(n+1)=2n3+3n2+2n+1=(n3)

练习解答【算法A】

矩阵乘法A×B=C,A/B/C均为