文档介绍：*
注意
算法是程序设计的灵魂
*
与数据结构的区分：
考虑问题的角度：数据结构关切不同的数据结构在解题中的作用和效率；算法关切不同设计技术的适用性和效率。
考虑问题的高度：数据结构关切的是解具体问题，算法不仅如此，它供应y;
(a) (b) (c)
分析：
(a)： x=x+y执行了1次
(b)： x=x+y执行了n次
(c)： x=x+y执行了n2次
注：在事前分析中，只限于确定与所运用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。
算法分析
*
数量级
语句的数量级：语句的执行频率。例：1，n ，n2

算法的数量级：算法包含全部语句的执行频率之和。
算法的数量级从本质上反映了一个算法的执行特性。
例：求解同一问题的三个算法分别具有n, n2 , n3数量级。
若n=10，则可能的执行时间将分别是10，100，1000 个单位时间——与环境因素无关。
算法分析
*
算法分析
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;
*
算法分析
线性阶
时间困难度为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）
*
算法分析
平方阶
时间困难度为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）
*
算法分析
多项式阶
时间困难度为O(nd) d为固定常数
算法运行时间随着问题的规模而成d次多项式阶变更
对数阶 O(logn)
指数阶 O(log2n)
阶乘阶 O(n!)
………
若T(n) = adnd+…+a1n+a0是一个d次多项
式，则有T(n)=O(nd)
*
5、算法分类（计算时间）
多项式时间算法：可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
Ο(1) < Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
指数时间算法：计算时间用指数函数限界的算法
常见的指数时间限界函数：
Ο(2n) < Ο(n！) < Ο(nn)
说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上特别悬殊。
算法分析
*
计算时间的数量级对算法有效性的影响
数量级的大小对算法的有效性有确定性的影响。
例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则：
n=1024：分别须要1048576和10240次运算。
n=2048：分别须要4194304和22528次运算。
分析：在n加倍的状况下，一个Ο(n2)的算法计算时间增长4倍，而一个Ο(nlogn)算法则只用两倍多一点的时间即可完成。
算法分析
*
典型的计算时间函数曲线
结论：在依次处理机上扩大所处理问题的规模，最有效的途径是降低算法计算困难度的数量级，而不是（仅仅依靠）提高计算机的速度。
算法分析
*
查找算法
所谓查找（search），即依据给定的某个值，在一组数据（如一个数组）中，确定有没有出现