数据结构第2章 算法分析.ppt

算法算法的定义算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。输入
输出
有穷性
确定性
可行性输入:作为算法加工对象的量值，通常体现为算法中的一组变量。有穷性:对于任意一组合法输入值，在执行有穷步骤之后一定能结束。即：算法中的每个步骤都能在有限时间内完成。确定性:对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。可行性:算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。算法设计的原则首先，算法应当满足以特定的“规格说明”方式给出的需求。c．程序对于精心选择的、典型的、苛刻的且带有刁难性的几组输入数据能够得出满足要求的结果；算法主要是为了人的阅读与交流，其次才是为计算机执行。
因此算法应该易于人的理解。
另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。
并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。高效率与低存储量需求算法分析：对算法的执行时间和需要的存储空间进行定性分析，以比较算法、改进算法。空间复杂度分析分析模型
运行时间的计算
运行时间中的对数
分析模型-渐进表示法要分析的问题：渐进时间复杂性分析方法：(a){++x;s=0;}语句频度为1，T(n)=O(1)

选
择
排
序常见函数的时间复杂度按数量递增排列及增长率。
常数阶O(1)
对数阶O(logn)
对数平方O(log2n)
线性阶O(n)
线性对数阶O(nlogn)
平方阶O(n2)
立方阶O(n3)
……
k次方阶O(nk)
指数阶O(2n)
如果存在正常数c和n0，当N>n0，
T(N)≤cf(N)，则记为T(N)=O(f(N))。分析模型-渐进表示法f(n)=Ω(g(n))的表示意味着f(n)渐进大于或等于g(n)，
因此从渐进的意义上来说，g(n)是f(n)的下界。T1(n)=Ω(n)
T2(n)=Ω(log2n)f(n)=Θ(g(n))的表示意味着f(n)渐进等于g(n)。规则1：
用函数乘以或除以一个正常量不会改变它的阶
3n2和0.2n2都在Θ(n2)例题1：T1(n)=3n+1与T2(n)=5log2n+7哪个快？练习1例题3：比较哪个速度快
T1(n)=an3+bn2+c
T2(n)=n(n+1)/2例题4：比较哪个速度快
T1(n)=an3
T2(n)=n!时间复杂度publicintsum(intn){
intpartialSum;
partialSum=0;
for(inti=1;i<=n;i++)
partialSum+=i*i*i;
returnpartialSum;
}publicintsum(intn){
intpartialSum;
partialSum=0;
for(inti=1;i<=n;i++)
partialSum+=i*i*i;
returnpartialSum;
}for(i=1;i<n;i++)
for(j=0;j<n;j++)
k++;for(i=0;i<n;i++)
a[i]=0;
for(i=1;i<n;i++)
for(j=0;j<n;j++)
a[i]+=a[j]+i+j;运行时间计算—一般法则运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间计算—举例运行时间中的对数运行时间中的对数-举例1运行时间中的对数-举例1运行时间中的对数-举例1算法分析运行时间中的对数-举例1运行时间中的对数-举例2小结