计算机算法基础-修改.doc

算法就是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法的五个重要特征：（1）确定性（2）能行性（3）输入（4）输出（5）有穷性算法与计算过程的区别：凡是算法，都必须满足以上五条特性。只满足前四条特性的一组规则不能称为算法，只能叫做计算过程。制定一个算法必经的阶段：设计、确认、分析、编码、检查、调试、计时学习算法应该涉及的内容：（1）如何设计算法（2）如何表示算法（3）如何确认算法（4）如何分析算法（5）如何测试程序时空分布图是用各种给定的数据执行调试认为是正确的程序，并测定为计算出结果所花去的时间和空间，以印证以前所作的分析是否正确和指出实现最优化的有效逻辑位置。算法分析方式分类：事前分析和事后测试。事前分析求出该算法的一个时间限界函数（它是一些有关参数的函数）。事后测试收集此算法的执行时间和实际占用空间的统计资料。4页?下标？上界：如果存在两个正常数c和n0，对于所有的n=n0,有 |f(n)|c|g(n)|则记作f(n)=O(g(n)6页? 下标？下界：如果存在两个正常数c和n0，对于所有的nn0，有 |f(n)|c|g(n)| 则记作f(n)=(g(n)6页?下标？确界：如果存在正常数c1,c2和n0，对于所有的nn0，有c1|g(n)|f(n)|c2|g(n)| 则记作f(n)= (g(n)计算时间的多项式时间算法关系：数量级O(1)O(logn)O(n)O(nlogn)O(n)O(n)？上标？5页 指数级O(2 n)O(n!) 0/xmaxA(1)；j1for i2 to n doif A(i)xmax then xmax A(i)；j i；endifrepeatend MAX假定A（1：n）是实数数组，这个过程的完整说明如下：procedure MAX(A，n，j) global real xmax；parameters integer j，n；real A(1：n)local integer i；栈和队列是两种特殊的有序表。栈是所有的插入和删除都在栈顶的表的一端进行。而队列的所有插入只能在尾总的一端进行，所有的删除只能在前部的另一端进行。栈是一个后进先出LIFO表。队列的运算要求第一个插入队中的元素也第一个被移出，是一个先进先出FIFO表。栈和队列表示方法：一种是用一个一维数组表示，另一种是使用链接表表示。？下标？ 树是一个或多个结点的有限集合，它使得：有一个特别指定的称作根的结点；剩下的结点被分成m0个不相交的集合T1，Tm，这些集合的每一个都是一棵树，并称T1，Tm为这根的子树。森林是m0个不相交树的集合。若去掉树的根，就得到一个森林。层又叫级，设根是1级，若某结点在p级，则它的儿子在p+1级。一棵树中结点的最大级数定义为该树的高度或深度。二元树是结点的有限集合，它或者为空，或者由一个根和两棵树（称之为左子树、右子树）的不相交的二元树所组成。二元树特性：任何一个结点至多只能有两个儿子，即不存在度大于2的结点；另外，二元树的子树是有次序之分的，即分为左子树和右子树，而树的子树实际上无次序之分；再者，二元树允许有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=1 Fi= Fi -1+F i -2 i1算法1.7求斐波那契数procedure F(n) /返回第n个斐波那契数 / inteqer n if n1 then return(1) else return(F(n-1)+F(n-2)endif end F eg1.5：已知元素x，判断x是否在A（1：n）中。算法1.9 在A（1：n）中检索xprocedure SEARCH(i) /如果在A（1：n）中有一元素A(k)=x，则将其第一次出现的下标k返回，否则返回零/ global n，x，A（1：n） case ：in：return(0) ：A(i)=x：return(i) ：else：return(SEARCH(i+1) endcase end SEARCH定理：设A（1：n）含有n(n1)个不同的元素，排序为A(1)2？上标？当n是2的幂时，即对于某个正整数k，n=2k，有？上标、求和式？T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2 =2k-1T(2)+ ?2i=2k-1+2k-2=3n/2-2?大括号？46页 下式C(n)=2 n=2 2C(n/2)+3 n2解此关系式可得？上标、求和式46页？C(n)=2C(n/2)+3=4C(n/4)+6+3 =2k-1C(2)+3 ?2i=2k+32k-1-3=5n/2-3如果归并运算的时间与n成正比，则归并分类的计算时间可用递归关系式描述如下：?大括号？下式T(n)=a n=1,a 是常数 2T(n/2)+cn n1,c是常数？上标？ 49页当n是2的幂即n=2k时，可以通过逐次代入求出其解：T(n)=2(2T(n/4)+cn/2)+cn=4T(n/4)+2cn=4(2T(n/8)+cn/4)+2cn =2kT(1)+kcn=an+cnlogn如果2kn2其中，a和b是常数。求解这个递归关系式，得 ？64页 上标T(n)= an (1+7/4+(7/4)+(7/4)k-1)+7kT(1)cn (7/4)logn+7 logn c是一个常数=cnlog4+log7-log4+nlog7=(c+1)nlog7=O(nlog7)O(n2.81)把那些必须满足的条件称为约束条件；而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以函数形式给出，这些函数称为目标函数。那些使目标函数取极值(极大或极小)的可行解，称为最优解。贪心方法是一种改进了的分级处