算法引论及简单算法.ppt

算法引论及简单算法
第1页，共37页，编辑于2022年，星期一
*
注 意
算法是程序设计的灵魂
第2页，共37页，编辑于2022年，星期一
*
与数据结构的区别：
考虑问题的角度：数据结构关心不同的数据结构在辑于2022年，星期一
*
频率计数：算法中语句或运算的执行次数。

例：
x=x+y for (i =1;i<=n;i++) for (i =1;i<=n;i++)
x=x+y; for (j =1;j<=n;j++)
x=x+y;
(a) (b) (c)
分析：
(a)： x=x+y执行了1次
(b)： x=x+y执行了n次
(c)： x=x+y执行了n2次
注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。
算法分析
第14页，共37页，编辑于2022年，星期一
*
数量级
语句的数量级：语句的执行频率。例：1，n ，n2

算法的数量级：算法包含所有语句的执行频率之和。
算法的数量级从本质上反映了一个算法的执行特性。
例：求解同一问题的三个算法分别具有n, n2 , n3数量级。
若n=10，则可能的执行时间将分别是10，100，1000 个单位时间——与环境因素无关。
算法分析
第15页，共37页，编辑于2022年，星期一
*
算法分析
5、算法复杂性的等级
常量阶
时间复杂度为O(1)
算法运行时间不随着问题的规模而变化
如：
简单的赋值语句， x=y;
算术运算， x=y*5+z%3;
固定次数的循环语句等
for (i=0;i<10;i++)
for (j=0;j<20;j++)
a[i][j]=0;
第16页，共37页，编辑于2022年，星期一
*
算法分析
线性阶
时间复杂度为O(n)
算法运行时间随着问题的规模而成线性变化
for (i=0;i<n;i++)
sum=sun+i;
算法执行了多少次运算？
i=0; 执行了1次
i<n; 执行了n+1次
i++； 执行了n次
sum=sun+i;执行了n次
共执行了3n+2次运算
时间复杂度就是O（3n+2）
实际上，算法的时间复杂度并不精确计算基本操作的执行次数，它主要考虑问题规模的增长率。 O（n）
第17页，共37页，编辑于2022年，星期一
*
算法分析
平方阶
时间复杂度为O(n2)
算法运行时间随着问题的规模而成平方变化
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
sum=sun+a[i][j]; //执行n2次
}
printf(“%dn”,sum); //执行n次
}
时间复杂度就是O（n2）
第18页，共37页，编辑于2022年，星期一
*
算法分析
多项式阶
时间复杂度为O(nd) d为固定常数
算法运行时间随着问题的规模而成d次多项式阶变化
对数阶 O(logn)
指数阶 O(log2n)
阶乘阶 O(n!)
………
若T(n) = adnd+…+a1n+a0是一个d次多项
式，则有T(n)=O(nd)
第19页，共37页，编辑于2022年，星期一
*
5、算法分类（计算时间）
多项式时间算法：可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法：计算时间用指数函数限界的算法
常见的指数时间限界函数：
Ο(2n) < Ο(n！) < Ο(nn)