算法分析与设计(王继成)：算法第1章

《算法分析与设计(王继成)：算法第1章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2014/3/8计算机算法设计与分析第1章算法概述学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C++语言描述算法的方法。算法(Algorithm)程序(Program)算法是指解决问题的一种方法或一个过程。程序是算法用某种程序设计语言的具体实现。算法是若干指令的有穷序列，满足性质：程序可以不满足算法的性质(4)。(()1)输入：有外部提供的量作为算法的输入。例如操作系统，是一个在无限循环中执行的程序，因(2)输出

2、：算法产生至少一个量作为输出。而不是一个算法。(3)确定性：组成算法的每条指令是清晰，无歧义的。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。(4)有限性：算法中每条指令的执行次数是有限的，执该子程序得到输出结果后便终止。行每条指令的时间也是有限的。问题求解(ProblemSolving)算法复杂性分析理解问题算法复杂性=算法所需要的计算机资源精确解或近似解选择数据结构算法的时间复杂性T(n)；算法设计策略算法的空间复杂性S(n)。设计算法其中n是问题的规模（输

3、入大小）。证明正确性分析算法设计程序12014/3/8算法的时间复杂性算法渐近复杂性（1）最坏情况下的时间复杂性T(n),asn;Tmax(n)=max{T(I)

4、size(I)=n}(T(n)-t(n))/T(n)0，asn;（2）最好情况下的时间复杂性t(n)是T(n)的渐近性态，为算法的渐近复杂性。Tmin(n)=min{T(I)

5、size(I)=n}在数学上，t(n)是T(n)的渐近表达式，是T(n)略去低阶（3）平均情况下的时间复杂性项留下的主项。它比T(n)简单。Tavg(n)

6、=p(I)T(I)size(I)n其中I是问题的规模为n的实例，p(I)是实例I出现的概率。（3）非紧上界记号o渐近分析的记号o(g(n))={f(n)

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

8、存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}(g(n))={f(n)

9、对于任

10、何正常数c>0，存在正数和n0（2）渐近下界记号>0使得对所有nn0有：0cg(n)

11、存在正常数c和n0使得对所有nn0有：等价于f(n)/g(n)，asn。0cg(n)f(n)}f(n)(g(n))g(n)o(f(n))渐近分析记号在等式和不等式中的意义（5）紧渐近界记号(g(n))={f(n)

12、存在正常数c1,c2和n0使得对所有nn0f(n)=(g(n))的确切意义是：f(n)(g(n))。有：c1g(n)f(n)c2g(

13、n)}一般情况下，等式和不等式中的渐近记号(g(n))表示(g(n))中的某个函数。定理1：(g(n))=O(g(n))(g(n))例如：2n2+3n+1=2n2+(n)表示2n2+3n+1=2n2+f(n)，其中f(n)是(n)中某个函数。等式和不等式中渐近记号O,o,和的意义是类似的。22014/3/8渐近分析中函数比较渐近分析记号的若干性质f(n)=O(g(n))ab;（1）传递性：f(n)=(g(n))ab;f(n)=(g(n))，g(n)=(h(n))f(n)=

14、(h(n))；f(n)=(g(n))a=b;f(n)=O(g(n))，g(n)=O(h(n))f(n)=O(h(n))；f(n)=o(g(n))ab.f(n)=o(g(n))，g(n)=o(h(n))f(n)=o(h(n))；f(n)=(g(n))，g(n)=(h(n))f(n)=(h(n))；（2）反身性：f(n)=(f(n))；（5）算术运算：f(n)=O(f(n

15、))；O(f(n))+O(g(n))=O(max{f(n),g(n)})；f(n)=(f(n)).O(f(n))+O(g(n))=O(f(n)+g(n))；（3）对称性：O(f(n))*O(g(n))=O(f(()n)*g(n))；f(n)=(g(n))g(n)=(f(n)).O(