《算法技术手册》一3.5.2 输入/输出

前言 修订一本书向来都是一项艰巨的任务.我们既希望保留第1版(于2009年出版)中的精华,也希望弥补其中的一些不足并增加一些新的篇幅.在第2版中,我们延续了第1版中列出的原则,包括: 使用实际代码而非伪代码来描述算法. 将算法独立于解决的问题之外. 恰到好处地介绍数学知识. 以经验主导支撑数学分析. 在更新修订过程中,我们精简了文字描述,简化了一些布局,从而有助于补充新的算法和其他内容.我们相信,从概括的角度介绍计算机科学的一个重要领域,会对实用软件系统有着深远影响. 第2版的变动 在修订过程中

3.1 算法模板的格式 使用模板来描述算法的好处在于可以很方便地对比各种算法的相似和不同之处.本书中的每种算法都会遵照模板格式使用固定的小节进行展示.如果某个小节不适用于当前算法或者没有什么价值,就会略去. 3.1.1 名称 算法的描述性名称,用来方便区分其他算法.例如,当我们讨论顺序搜索时,这个名称可准确表达所讨论的是哪种搜索算法.算法的名称永远用粗体表示. 3.1.2 输入/输出 描述输入/输出数据的格式和结构. 3.1.3 使用环境 使用环境一节描述了算法的最佳使用时机和场所,还有成功实现

2.1 问题样本的规模 问题样本是解决问题的程序所使用的特定输入数据集.在大部分问题中,随着这一数据集规模的增长,程序的执行时间也在不断增加.同时,过度地对样本数据进行编码(可能使用了压缩技术),可能会不必要地降低程序的执行效率.寻找一种最优的样本编码方式是极其困难的,因为问题发生在复杂的现实世界,而且还需要进行合理的翻译才能被程序求解. 在评估算法时,我们会尽量假定问题样本的编码并不是影响算法效率的决定性因素.问题样本的表现方式应当仅仅依赖于待执行操作的类型.设计高效的算法通常从选择一个合适的

2.4.7 性能不明显的计算 在很多情况下,仅仅通过算法的描述(如加法和乘法)就可以分辨出算法的性能是线性级还是平方级的.例如,平方级的主要特征是嵌入的循环结构.但是,这样的直接分析对某些算法却无法使用.例2-5给出了GCD算法,该算法是由欧几里德设计,用于计算两个整数的最大公约数. 例2-5:欧几里得GCD 算法 public static void gcd (int a[], int b[], int gcd[]) { if (isZero (a)) { assign (gcd, a); r

2.2 函数的增长率 我们将算法执行时间的增长率描述为一个与输入问题样本规模相关的函数.使用这种方法描述算法性能会比较抽象,因为它忽略了大量的细节问题.所以,在使用这种方法时,需要对抽象背后的细节有一个清醒的认识.程序都必须运行在某个平台上,在这里,广义的平台定义包括: 运行程序的计算机,包括CPU.数据缓存.浮点运算单元(FPU)以及其他芯片特性. 程序编写所使用的编程语言.编译器/解释器以及用于生成代码的优化设置. 操作系统. 其他后台进程. 改变上述组成平台的任何条件都只会对程序的执行时间

1.3.5 融会贯通 通常,解决某一类问题的算法和解决某一个特定问题的算法是大致相通的.Voronoi图(Preparata and Shamos,1993)是这样一个几何结构--它可以将平面上的点集划分成多个区域,其中每个区域的重心点为输入集P中的点.每个区域Ri中任意一点(x, y)到Pi的距离都比到其他区域的重心点要近.图1-7展示了计算出的Voronoi图.灰色区域是半无限的,并且灰色区域的重心点组成了凸包.由此可以得出以下算法: 1. 计算输入集P的Voronoi图. 2. 将P中的最

1.2 简单解法 很显然,任意包含三个或三个以上点的点集都肯定有凸包.但是如何构建一个凸包呢?可以这么考虑,从上述集合中选择任意三个点组成一个三角形,如果剩余的n-3个点中的任意一个位于该三角形之内,那么这些位于内部的点是不可能成为凸包的一部分的.我们可以用伪代码描述大致流程.本书其他章节也会采用类似的伪代码来描述算法.在下一章中,我们将从数学的角度解释为什么这个方法非常低效.这段伪代码摘要解释了如何针对每个输入集生成一个凸包,特别是,像图1-2所示的凸包.不过,难道没有更好的做法了吗?

2.3.4 上下界 在本书中,我们简化了"大O"表示法,目的是对不同问题样本在持续增长的规模n下算法性能进行分类.这种分类使用O(f(n))表示,其中f(n)是一些如n.n3或者2n的常见函数.例如,假设存在一个算法,当输入数据规模"足够大"时,它在最坏情况下的性能绝不大于和输入问题样本规模成比例的某个值.更加精确地说,对于所有的n > n0,存在某个常数c > 0,满足t(n) ≤ cn ,其中n0是每个问题样本"足够大时"的基本点

3.5.1 算法名称和摘要 Graham扫描算法可以计算出笛卡儿空间给定点集的凸包.它首先会寻找输入集P中的最低点low,然后将剩下的点{P-low}按照和low的极角从大到小排序.之后算法会按序遍历这些点构建凸包,如果凸包上最新的三个点构成一个左拐,那么最新加入的点就需要被删除掉.