《算法技术手册》一1.2 简单解法

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

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

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

3.4 浮点计算由于书中的某些算法需要使用到数值计算,因此这里需要简单讲述一下现代计算机在数值计算中的作用以及某些先天不足.众所周知,计算机是对存储在CPU寄存器的值进行一些基本运算.随着计算机架构从20 世纪70 年代流行的8位Intel处理器演进到如今广泛存在的64位架构(如Intel的Itanium以及Sun的Sparc处理器),寄存器的大小也随之发生了翻天覆地的变化.CPU通常支持对存储在寄存器的整数进行一些基本的运算,例如ADD.MULT.DIVIDE和SUB.浮点计算则交给了浮点运算

第3章 算法基础 虽说开发软件是为了解决问题,但程序员们往往太执着于是否能够解决问题本身,而不去确认这一问题是否已有解决之法.即便程序员们知道前人已在类似情况下解决了问题,但"已有的解决之法"最终是否适用于特写的问题仍是一个未知数.更重要的是,要找到完全不需要修改或者只需要稍作修改便能解决手头问题的代码并不容易.不同的人对待算法的态度各有千秋.很多人就只是简单地在一本书中或者网站上找个算法,复制代码,运行一次,然后可能还会测试一次,如果结果正确,就开始做下一个任务.但是,在我们看来,这

3.2 伪代码模板的格式 本书中的每个算法都可以用主流的编程语言实现,例如Python.C.C++ 和Java.由于有些读者不熟悉这些语言,我们会先用伪代码描述算法,并辅以一个小例子来解释运行过程.下面的例子给出了描述算法性能的模板,它包含算法名称,以及第2章中所述的算法的三个性能指标(最好情况.平均情况和最坏情况).伪代码的描述应当尽可能得简洁.其中关键字和函数名称用粗体字表示,所有变量采用小写字母,数组名称大写,元素采用A[i]这样的表示形式.条件语句和循环语句需要缩进.在阅读代码实现之前,

3.6.3 动态规划 动态规划是分治算法的一个衍生,它将一个问题切分成多个更加简单的子问题,然后按照顺序逐个解决.对于每个子问题,它只求解一次,然后将结果存储起来以供后续使用,这样可以避免重复计算.此外,动态规划在计算当前解时,会结合较小规模的子问题的解,并且不断增加子问题的规模.很多情况下,最终计算出来的解即为全局最优解.动态规划常用于求解最值优化类问题上.下面通过一个示例来阐释动态规划算法.科学家经常通过比对DNA序列来确定其相似性.现有这样一个DNA序列--由A.C.T.G所组成.因此,一

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

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