第1章 《算法分析与设计》算法概述ppt课件.ppt

《第1章 《算法分析与设计》算法概述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计电子与电气工程系通信教研室任课老师：温洪明第一章概论1.1数据结构的基本概念1.2数据结构的基本术语1.3算法描述1.4算法分析算法概述学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。算法（Algorithm）算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰，无

2、歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。程序（Program）程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。问题求解（ProblemSolving）设计算法证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略算法复杂性分析算法复杂性=算法所需要的计算机资

3、源时间复杂度当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占用的空间也以某种单位从1增加到T(n)，那么算法的空间复杂度为T(n)。T(n)=O(f(n))通常用O(1)表示常数计算时间，常用的渐进时间复杂度为有O(1)

4、成分（如数组元素、结构成分、对象的数据成员等）变量所占的空间与问题的输入规模无关可变部分与问题规模有关的变量所占空间、递归栈所用的空间通过new和delete命令动态使用的空间定义通常以算法的空间复杂度作为算法所需要的存储空间的量度。定义如下：S(n)=O(g(n))空间复杂度的估算固定部分做简单的统计即可问题规模n相关的变量根据算法说明，给出和n的函数关系对于递归算法，需要考虑递归深度和每次调用需要的空间动态存储分配的空间考虑最坏的情况：MAX（new的执行次数-delete执行次数）算法的时间复杂性（1）最坏情况下的时间复

5、杂性Tmax(n)=max{T(I)

6、size(I)=n}（2）最好情况下的时间复杂性Tmin(n)=min{T(I)

7、size(I)=n}（3）平均情况下的时间复杂性Tavg(n)=啊啊啊啊啊啊啊其中I是问题的规模为n的实例，p(I)是实例I出现的概率。算法渐近复杂性一般而言，当n单调增加且趋于无穷大时，T(n);对于T(n)如果存在t(n)使得n时有(T(n)-t(n))/T(n)0，那么就说t(n)是T(n)当n时的渐进性态，或者称t(n)为算法的渐进复杂性。t(n)是T(n)的渐近性态，为算法的渐近复杂性

8、。在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n)简单。例如一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3，则T(n)=O(n3)渐近分析的记号在下面的讨论中，对所有n，f(n)0，g(n)0。（1）渐近上界记号OO(g(n))={f(n)

9、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}（2）渐近下界记号(g(n))={f(n)

10、存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}（3）非紧上界记号oo(g(n))={f(n)

11、对

12、于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)

13、对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)

14、存在正常数c1,c2和n0使得对所有nn0有：c1g(n)f(n)c2g(n)}定理1：(g(n))=O(

15、g(n))(g(n))渐近分析记号在等式和不等式中的意义f(n)=(g(n))的确切意义是：f(n)(g(n))。一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数。例如：2n2+3n+1=2n2+(n)表示2n2+3n+1=2n2+