计算机算法基础-修改

《计算机算法基础-修改》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法的五个重要特征：（1）确定性（2）能行性（3）输入（4）输出（5）有穷性算法与计算过程的区别：凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。制定一个算法必经的阶段：设计、确认、分析、编码、检查、调试、计时学习算法应该涉及的内容：（1）如何设计算法（2）如何表示算法（3）如何确认算法（4）如何分析算法（5）如何测试程序时空分布图是用各种给定的数据执行调试认为是正确的程序，并测定为计算出结果所花去的时间和空间，以印证以前所作

2、的分析是否正确和指出实现最优化的有效逻辑位置。算法分析方式分类：事前分析和事后测试。事前分析求出该算法的一个时间限界函数（它是一些有关参数的函数）。事后测试收集此算法的执行时间和实际占用空间的统计资料。4页?下标？上界：如果存在两个正常数c和n0，对于所有的n>=n0,有

3、f(n)

4、≤c

5、g(n)

6、则记作f(n)=O(g(n))6页?下标？下界：如果存在两个正常数c和n0，对于所有的n>n0，有

7、f(n)

8、≥c

9、g(n)

10、则记作f(n)=Ω(g(n))6页?下标？确界：如果存在正常数c1,c2和n0，对于所有的n>n0，有c1

11、g(n

12、)

13、≤

14、f(n)

15、≤c2

16、g(n)

17、则记作f(n)=Θ(g(n))计算时间的多项式时间算法关系：数量级O(1)0//xmax←A(1)；j←1fori←2tondoifA(i)>xmaxthenxmax←A(i)；j←i；endifrepeatendMAX假定A（1：n）是实数数组，

18、这个过程的完整说明如下：procedureMAX(A，n，j)globalrealxmax；parametersintegerj，n；realA(1：n)localintegeri；栈和队列是两种特殊的有序表。栈是所有的插入和删除都在栈顶的表的一端进行。而队列的所有插入只能在尾总的一端进行，所有的删除只能在前部的另一端进行。栈是一个后进先出LIFO表。队列的运算要求第一个插入队中的元素也第一个被移出，是一个先进先出FIFO表。栈和队列表示方法：一种是用一个一维数组表示，另一种是使用链接表表示。？下标？树是一个或多个结点的有限集合，它使

19、得：①有一个特别指定的称作根的结点；②剩下的结点被分成m≥0个不相交的集合T1，…，Tm，这些集合的每一个都是一棵树，并称T1，…，Tm为这根的子树。森林是m≥0个不相交树的集合。若去掉树的根，就得到一个森林。层又叫级，设根是1级，若某结点在p级，则它的儿子在p+1级。一棵树中结点的最大级数定义为该树的高度或深度。二元树是结点的有限集合，它或者为空，或者由一个根和两棵树（称之为左子树、右子树）的不相交的二元树所组成。二元树特性：任何一个结点至多只能有两个儿子，即不存在度大于2的结点；另外，二元树的子树是有次序之分的，即分为左子树和右子

20、树，而树的子树实际上无次序之分；再者，二元树允许有0个结点，而一棵树至少要有一个结点。完全二元树：一棵有n个结点深度为k的二元树，当它的结点相当于深度为k的满二元树中编号为1到n的结点时，则称此二元树是完全的。图G由称之为结点V和边E的两个集合所组成。顺序表示使用n行和n列的方阵表，其中n是结点数，这个表称为邻接矩阵。邻接链表表示是由n个表组成的，每个结点i有一个表，这个表由i所邻接的那些结点所组成。eg1.3：斐波那契序列1，1，2，3，5，8，13，21，34，…的定义为F0=F1=1Fi=Fi-1+Fi-2i>1算法1.7求斐波

21、那契数procedureF(n)//返回第n个斐波那契数//inteqernifn≤1thenreturn(1)elsereturn(F(n-1)+F(n-2))endifendFeg1.5：已知元素x，判断x是否在A（1：n）中。算法1.9在A（1：n）中检索xprocedureSEARCH(i)//如果在A（1：n）中有一元素A(k)=x，则将其第一次出现的下标k返回，否则返回零//globaln，x，A（1：n）case：i>n：return(0)：A(i)=x：return(i)：else：return(SEARCH(i+1)

22、)endcaseendSEARCH定理：设A（1：n）含有n(n≥1)个不同的元素，排序为A(1)<…