acm程序设计复习提纲

《acm程序设计复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ACM程序设计复习提纲1、排序算法：掌握合并排序、插入排序、快速排序的算法思想、伪代码实现、算法效率的差别之处思想：把一个数组不断的对半拆分，直到拆到最小，然后把已拆好的数组再进行合并，合并过程中进行大小的比较，最终形成一个排好序的数组。效率分析：算法的时间主要消耗在求解最小规模问题的解G(p,q)、划分问题DIVIDE(p,q)、合并子问题的解三个部分。计DANDC的时间为T(n)，G(p,q)的时间为g(n)，DIVIDE(p,q)的时间为f(n)，由于合并子问题的解是递归调用了DANDC，因此这一部分的时间为2T(n/2)因此DANDC的时间T

2、(n)当输入规模足够小的时候为g(n)，其他时候为划分时间与合并子问题解的时间之和，即2T(n/2)+f(n)合并算法的计算时间：当n=2k时，可得T(n)=2(2T(n/4)+n/2)+n=4T(n/4)+2n=4(2T(n/8)+n/4)+2n……=2kT(1)+kn=nlogn如果2k

3、plitposition).递归拆分下去，直到分区仅有一个元素为止。建立分区时完成了元素的重排，拆分结束即排序结束Partition(A[L...R]){p←A[L]//选择中轴i←L+1,j←R//左右扫描位置指针。左扫描没找到时，i停在L+1位置while(true){while(A[i]p)and(j≥L)doj←j-1//右扫描（带限位）if(i≥j)thenbreak//左右扫描已交叉，退出循环swap(A[i],A[j])//左右扫描未交叉}swap(A[L],

4、A[j])return(j)//返回分裂点j}插入排序假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性算法的时间复杂度　　1、求两个正整数的最大公约数、最小公倍数。掌握欧几里德算法（算法收敛）gcd(m,n)的欧几里得算法第一步：如果n=0，返回m的值作为结果，结束；否则进入第二步第二步：用n去除m，将余数赋给r。第三步：将n的值赋给m，将r的值赋给n，回第一步。算法Eucl

5、id(m,n)//使用欧几里得算法计算gcd(m,n)//输入：两个不全为0的非负整数m,n//输出：m，n的最大公约数Whilen!=0dorßmmodnmßnnßrReturnm两个数的最小公倍数=两个数的乘积除以两个数的最大公约数2、怎样评价算法的效率，掌握评价算法框架。（PPT第二章）分析算法（1）算法有两种效率：时间效率和空间效率（2）算法的另外两个特性：简单性和一般性算法效率分析基础l算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法分析l需解决的问题¡度量一个算法的时间效率(时间费用)¡度量一个算法的空间效率(空间费用)¡

6、优化算法l最小化一个算法的时间效率或空间效率l途径¡理论分析¡经验分析分析框架——输入规模度量l输入规模度量¡算法的时间效率和空间效率都用输入规模的函数进行度量。¡对于所有的算法，对于规模更大的输入都需要运行更长的时间。¡经常使用一个输入规模n为参数的函数来研究算法的效率。¡选择输入规模的合适量度，要受到所讨论算法的操作细节影响。分析框架——运行时间的度量单位1、耗费时间的度量为何不选择时间的标准度量（秒、毫秒等）度量算法的运行时间呢？——它依赖于特定计算机系统的运行速度——它依赖于实现算法的代码质量（程序员的编程水平）——它依赖于编译器的好坏（机器

7、码的质量，指令数和类型）——它依赖于一些其他问题，如操作系统的调度策略等希望找到一个不依赖于上述因素的时间度量。问：统计算法每步操作执行次数作为算法的时间度量，如何？答：无此必要，且分析复杂困难（若干变量）。一个算法有许多操作，决定算法耗时的是那些最费时的操作，因此，只需统计这些最费时的操作称为基本操作。它们对算法执行时间的占用最大。【结论】算法时间效率度量——基本操作的执行次数2、运行时间的度量单位用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。基本操作通常是算法最内层循环中最费时的操作。算法运行时间的估计：T(n)≈copC

8、(n)n是该算法的输入规模cop是特定计算机上一个算法基本操作的执行时间C(n)是该算法需要执行的基本操作的