《算法技术手册》一1.3.3 并行算法

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

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

3.5.4 解决方案 如果手动计算凸包,你应该可以很轻松地处理好各种极端情况.但是如果需要用计算机语言来描叙每一个步骤,我们可能会觉得比较困难.Graham扫描算法的关键点在于计算和最低点的极角大小.一旦计算并且排序之后,算法只需要遍历所有的点,不断地构建凸包并且根据新发现的信息调整结构即可.代码见例3-1. 例3-1:Graham扫描算法的实现 public class NativeGrahamScan implements IConvexHull { public IPoint[] comp

1.3 高明做法 本书介绍的大量算法都是在现有代码基础上对高效解法不懈追求的结果.我们努力地将这些算法实现为可用的代码,并尽量给出一些能够解决现实问题的算法.例如,对于凸包问题,就有许多不同的方法可以使用.在简述这些方法后,我们会在后续章节给出相应的示例.

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

1.3.1 贪心算法 以下的贪心算法展示了如何找到凸包上的每个点: 1. 删除P中的最低点low--low必须在凸包上. 2. 垂直画一条穿过点low的直线,将剩余的n-1个点分别和点low连线,以垂直直线右侧的点的夹角为正值降序排列,夹角的范围是从90皛-90啊n-2是最右侧的点,而P0是最左侧的点.图1-3中显示了垂直线以及每个点与其的夹角. 3. 以{Pn-2, low, P0}这个顺序组成的点集为基础,在剩余的点中选择可以组成凸包的点--从P1开始,将每个点尝试加至这个点集的尾部,如果

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

1.3.2 分治算法 我们也可以将点按x坐标从左到右排序(如果x坐标相同,就按照y坐标排序),就能将这个问题分成两个稍微小一点的子问题.首先可以从点p0到pn-1,按照从左到右.顺时针的顺序计算出一个上半部分凸包,然后用同样的方法从pn-1到p0,按照从右到左.同样是顺时针的顺序计算出下半部分凸包.凸包扫描算法(将在第9章中介绍)可以计算出这些半凸包(见图1-4),然后将结果合并在一起生成最终的凸包. 图1-4:合并上.下部分凸包组成完整凸包

3.5 算法举例 我们将通过Graham扫描算法来介绍本书的算法模板.该算法可以用于计算二维空间上给定点集的凸包(第1章已经介绍过这个问题,并在图1-3中予以说明).