《算法技术手册》一3.5 算法举例

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

2.4.3 次线性级算法O(nd)(d<1)的性能 在某些情况下,次线性算法的性能要好于线性算法,但还是不如对数算法高效.第10章将会讨论多维k-d树,它能够高效地划分n个d维的点.如果k-d树是平衡树,那么区间查询的性能为,在二维的情况下,最终性能为O(sqrt(n)).

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的极角从大到小排序.之后算法会按序遍历这些点构建凸包,如果凸包上最新的三个点构成一个左拐,那么最新加入的点就需要被删除掉.

前言 修订一本书向来都是一项艰巨的任务.我们既希望保留第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