《ACM程序设计复习提纲》由会员分享，可在线阅读，更多相关《ACM程序设计复习提纲（8页珍藏版）》请在金锄头文库上搜索。
1、ACM 程序设计复习提纲 1、 排序算法：掌握合并排序合并排序、插入排序插入排序、快速排序快速排序的算法思想、伪代码实现、算法效率 的差别之处 思想：把一个数组不断的对半拆分，直到拆到最小，然后把已拆好的数组再进行合并， 合并过程中进行大小的比较，最终形成一个排好序的数组。效率分析：效率分析： 算法的时间主要消耗在求解最小规模问题的解 G(p,q)、划分问题 DIVIDE(p,q) 、合 并子问题的解三个部分。 计 DANDC 的时间为 T(n)，G(p,q)的时间为 g(n)， DIVIDE(p,q) 的时间为 f(n)，由于 合并子问题的解是递归调用了 DANDC，因此这一部分的时间为 2
2、T(n/2) 因此 DANDC 的时间 T(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 p) and ( j L ) do jj-1 /右扫描（带限位）右扫描（带限位）if ( ij ) then break /左右扫描已交叉，退出循环左右扫描已交叉，退出循环swap(A i , A j ) /左右扫描未交叉左右扫描未交叉swap(A L,
3、A j )return ( j ) /返回分裂点返回分裂点 j插入排序插入排序 假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个 数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前 k 个数之后，可以保证 a1k是局部有序的，保证了插入过程的正确性算法的时间复杂度算法的时间复杂度2、 求两个正整数的最大公约数、最小公倍数。掌握欧几里德算法（算法收敛算法收敛） gcd(m,n)的欧几里得算法的欧几里得算法 第一步：如果第一步：如果 n=0，返回，返回 m 的值作为结果，结束；否则进入第二步的值作为结果，结束；否则进入第二步 第二步：用第
4、二步：用 n 去除去除 m，将余数赋给，将余数赋给 r。 第三步：将第三步：将 n 的值赋给的值赋给 m，将，将 r 的值赋给的值赋给 n，回第一步。，回第一步。 算法算法 Euclid(m,n) /使用欧几里得算法计算 gcd(m,n) /输入：两个不全为 0 的非负整数 m,n /输出：m，n 的最大公约数 While n!=0 dorm mod nmnnr Return m两个数的最小公倍数两个数的最小公倍数=两个数的乘积除以两个数的最大公约数两个数的乘积除以两个数的最大公约数 3、 怎样评价算法的效率，掌握评价算法框架。 （PPT 第二章） 分析算法分析算法 （1）算法有两种效率：时间
5、效率和空间效率）算法有两种效率：时间效率和空间效率 （2）算法的另外两个特性：简单性和一般性）算法的另外两个特性：简单性和一般性 算法效率分析基础算法效率分析基础 算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。 算法分析算法分析需解决的问题需解决的问题 度量一个算法的时间效率度量一个算法的时间效率(时间费用时间费用) 度量一个算法的空间效率度量一个算法的空间效率(空间费用空间费用) 优化算法优化算法 最小化一个算法的时间效率或空间效率最小化一个算法的时间效率或空间效率 途径途径 理论分析理论分析 经验分析经验分析 分析框
6、架分析框架输入规模度量输入规模度量 输入规模度量输入规模度量 算法的时间效率和空间效率都用输入规模的函数进行度量。算法的时间效率和空间效率都用输入规模的函数进行度量。 对于所有的算法，对于规模更大的输入都需要运行更长的时间。对于所有的算法，对于规模更大的输入都需要运行更长的时间。 经常使用一个输入规模经常使用一个输入规模 n 为参数的函数来研究算法的效率。为参数的函数来研究算法的效率。 选择输入规模的合适量度，要受到所讨论算法的操作细节影响。选择输入规模的合适量度，要受到所讨论算法的操作细节影响。 分析框架分析框架运行时间的度量单位运行时间的度量单位 1、 耗费时间的度量耗费时间的度量 为何不
7、选择时间的标准度量（秒、毫秒等）度量算法的运行时间呢？为何不选择时间的标准度量（秒、毫秒等）度量算法的运行时间呢？ 它依赖于特定计算机系统的运行速度它依赖于特定计算机系统的运行速度 它依赖于实现算法的代码质量（程序员的编程水平）它依赖于实现算法的代码质量（程序员的编程水平） 它依赖于编译器的好坏（机器码的质量，指令数和类型）它依赖于编译器的好坏（机器码的质量，指令数和类型） 它依赖于一些其他问题，如操作系统的调度策略等它依赖于一些其他问题，如操作系统的调度策略等 希望找到一个不依赖于上述因素的时间度量。希望找到一个不依赖于上述因素的时间度量。 问：统计算法问：统计算法 每步操作执行次数每步操作
8、执行次数 作为算法的时间度量，如何？作为算法的时间度量，如何？ 答：无此必要，且分析复杂困难（若干变量）答：无此必要，且分析复杂困难（若干变量） 。一个算法有许多操作，决定算法耗时的是那些一个算法有许多操作，决定算法耗时的是那些 最费时最费时 的操作，的操作，因此，只需统计这些最费时的操作称为基本操作。它们对算法因此，只需统计这些最费时的操作称为基本操作。它们对算法执行时间的占用最大。执行时间的占用最大。 【结论结论】算法时间效率度量算法时间效率度量 基本操作的执行次数基本操作的执行次数 2、运行时间的度量单位、运行时间的度量单位 用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时
9、间效率。用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。 基本操作通常是算法最内层循环中最费时的操作。基本操作通常是算法最内层循环中最费时的操作。 算法运行时间的估计：算法运行时间的估计：T(n) c opC(n)n n 是该算法的输入规模是该算法的输入规模c c opop是特定计算机上一个算法基本操作的执行时间是特定计算机上一个算法基本操作的执行时间C(n)C(n)是该算法需要执行的基本操作的次数是该算法需要执行的基本操作的次数分析框架分析框架增长次数增长次数增长次数增长次数小规模输入在运行时间上的差别不足以将高效的算法和低效的算法区分开来。小规模输入在运行时间上的差别
10、不足以将高效的算法和低效的算法区分开来。分析框架分析框架算法的最优、最差和平均效率算法的最优、最差和平均效率算法的最优、最差和平均效率算法的最优、最差和平均效率最差效率是指在输入规模为最差效率是指在输入规模为 n n 时，算法在最坏情况下的效率。时，算法在最坏情况下的效率。最优效率是指在输入规模为最优效率是指在输入规模为 n n 是，算法在最优情况下的效率。是，算法在最优情况下的效率。平均效率是指在平均效率是指在“典型典型”或或“随机随机”输入的情况下，算法具有的行为（效率）输入的情况下，算法具有的行为（效率） 。摊销效率是指对于同样的数据结构执行多次操作，然后分摊到每一次上。摊销效率是指对于
11、同样的数据结构执行多次操作，然后分摊到每一次上。渐近时间效率分析的概念渐近时间效率分析的概念 评估算法的时间复杂性，不需要且难以对执行时间作出精确的统计，有较高实时性要评估算法的时间复杂性，不需要且难以对执行时间作出精确的统计，有较高实时性要 求的例外（与硬件、语言、系统、编程等等相关）求的例外（与硬件、语言、系统、编程等等相关） 算法效率的主要指标是算法效率的主要指标是基本操作次数的增长次数基本操作次数的增长次数。 为了对这些增长次数进行比较和归类，计算机科学家们使用了为了对这些增长次数进行比较和归类，计算机科学家们使用了 3 3 种符号：种符号： O O（读（读“O”“O” ）：上界）：上
12、界 （读（读”omega”omega” ）：下界）：下界 （读（读”theta”theta” ）：近似）：近似 当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分 所决定。所决定。利用极限比较增长次数利用极限比较增长次数 非递归算法的数学分析非递归算法的数学分析： 1.1. 决定用那些参数作为输入规模的度量。决定用那些参数作为输入规模的度量。 2.2. 找出算法的基本操作。找出算法的基本操作。 3.3. 检查基本操作的执行次数是否只依赖输入规模。检查基本操作的执行次数是否只依赖输入规模。 4.4.
13、 建立一个算法基本操作执行次数的求和表达式。建立一个算法基本操作执行次数的求和表达式。 5.5. 利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它 的增长次数。的增长次数。 递归算法的数学分析递归算法的数学分析 决定用哪个参数作为输入规模的度量决定用哪个参数作为输入规模的度量 找出算法的基本操作找出算法的基本操作 检查对相同规模的输入，基本操作的执行次数是否相同，如果不同，必检查对相同规模的输入，基本操作的执行次数是否相同，如果不同，必 须对最差、平均及最优效率单独研究须对最差、平均及最优效率单独研
14、究 建立一个递推关系式及相应的初始条件建立一个递推关系式及相应的初始条件 求解这个递归关系式，或者至少确定解的增长次数求解这个递归关系式，或者至少确定解的增长次数 算法的经验分析算法的经验分析 算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析算法的经验分析是针对一个输入样本，运行算法的一个程序实现，然后分析 观测到的数据。观测到的数据。 对算法效率做经验分析的通用方案对算法效率做经验分析的通用方案 了解试验的目的了解试验的目的 决定用来度量效率的量度决定用来度量效率的量度 M M 和度量单位（单位时间内的操作次数）和度量单位（单位时间内的操作次数） 决定输入样本的特性决定输入
15、样本的特性 为实验准备算法的程序实现为实验准备算法的程序实现 生成输入样本生成输入样本 对输入样本进行计算，并记录观察到的实验数据对输入样本进行计算，并记录观察到的实验数据 分析获得的实验数据分析获得的实验数据4、 分治法解决凸包问题以及二维最近对，掌握思路以及算法描述。 最近对：在一个包含 n 个点的点集中，找到距离最近的两个点凸包问题：对于平面上的一个点集合（有限或无限） ，若果集合中任意两点 p 和 q 为端 点的线段都属于这个集合，则这个集合石凸的。 任意包含任意包含 n2 个点（不共线）的集合个点（不共线）的集合 S 的凸包是以的凸包是以 S 中的某些点为顶点的凸多边形。中的某些点为
16、顶点的凸多边形。 凸包问题是为一个凸包问题是为一个 n 个点的集合构造凸包的问题。个点的集合构造凸包的问题。 对于一个对于一个 n 个点集合中的两个点个点集合中的两个点 Pi和和 Pj，当且仅当该集合中的其他点都位于穿过这两，当且仅当该集合中的其他点都位于穿过这两 点的直线的同一边时它们的连线是该集合凸包边界的一部分。点的直线的同一边时它们的连线是该集合凸包边界的一部分。 假设假设 P1=(x1,x2),P(xn,yn)是平面上是平面上 n1 个点构成的集合个点构成的集合 S，并按，并按 X 轴坐标升轴坐标升 序排列，按序排列，按 Y 轴坐标升序建立连接。轴坐标升序建立连接。 则最左面和最右面的点一定是凸包的顶点。则最左面和最右面的点一定是凸包的顶点。5、减治法：图和树的拓扑排序
