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

《数据结构与算法分析第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第3章算法分析疑问？通常对一个问题有多种解决方法(算法),如何挑选一种较好的方法？→了解方法（算法）的相对效率。计算机编程的两大目标：设计理解容易、编码简单和调试方便的算法。→软件工程设计能够高效率地利用计算机资源的算法。→数据结构和算法分析如何检测算法的效率？实际测量算法的计算机运算时间。问题：1.需为每种算法都编写程序。2.代码质量对计算机耗时有影响。3.测试数据的选择对计算机耗时有影响。4.需要所有算法都运行一遍。渐近算法分析（简称算法分析）估算

2、算法及实现它的程序的效率和开销。计算机的关键资源时间代价空间代价（内存和磁盘空间）分析算法效率的可行方法可行的方法：一定规模下，算法所需基本运算的执行次数。基本运算的选择原则：1、算法执行的运算总次数与基本运算的次数大体上成比例。2、基本运算以外的其它运算的运算量可以忽略。影响运行时间的因素假设在代码质量、编译系统等与算法无关的因素相同的条件下，影响某算法程序执行时间的因素：1.问题的规模。运行时间T可以表示为规模n的函数T(n)。2.特定的输入。问题规模对运行时间的影响例1:查找数组元素中的最大值intlargest(intarray[],intn){intcurrlarge=0;//L

3、argestvalueseenfor(inti=1;i

4、算法代价的增长速率。线性增长率：T(n)=cn二次增长率：T(n)=cn2指数增长率：T(n)=c1c2C3n……特定输入对运行时间的影响例1:查找数组元素中的值为x的元素intSearchX(intarray[],intn){for(inti=1;i

5、n0，有T(n)≤cf(n)，则称T(n)在集合O(f(n))中。例：某一算法平均情况下T(n)=c1n2+c2n,c1,c2为正整数。若n>1，c1n2+c2n≤c1n2+c2n2。因此取c=c1+c2，n0=1，有T(n)≤cn2。故T(n)在O(n2)中。下限（大Ω表示法）描述算法消耗某

6、种资源（通常是时间）的最小值。对非负函数T(n)，若存在两个正常数c和n0，对任意n>n0，有T(n)≥cg(n)，则称T(n)在集合Ω(g(n))中。例：某一算法平均情况下T(n)=c1n2+c2n,c1,c2为正整数。若n>1，c1n2+c2n≥c1n2。因此取c=c1，n0=1，有T(n)≥cn2。故T(n)在Ω(n2)中。Θ表示法：如果一种算法既在O(h(n))中，又在Ω(h(n))中，则称其为Θ(h(n))。化简原则：计算某算法代价的渐近增长率时，忽略所有的常数和低次项。程序运行时间的计算例3.8a=b;该赋值语句执行时间为一个常量，因此时间代价为(1).例3.9sum=0;f

7、or(i=1;i<=n;i++)sum+=n;例3.10sum=0;for(i=1;i<=n;j++)for(j=1;j<=i;i++)sum++;for(k=0;k