《算法技术手册》一3.5.1 算法名称和摘要

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

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

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

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)以及其他芯片特性. 程序编写所使用的编程语言.编译器/解释器以及用于生成代码的优化设置. 操作系统. 其他后台进程. 改变上述组成平台的任何条件都只会对程序的执行时间

第2章 算法的数学原理 选择算法的一个很重要的考虑因素就是算法的执行速度.计算一个算法的期望执行时间本质上是一个数学运算过程.本章将透过现象看本质,阐述隐藏在算法时间预测背后的数学原理.在阅读本章之后,读者将能够理解本书中使用到的各类数学术语.这些术语贯穿全书,也时常出现在其他算法类书籍当中.

2.3.1 最坏情况 对于任一特定值n,算法或者程序在处理所有规模为n的样本时的执行时间可能会发生巨大的变化.对于一个给定的程序和一个给定的值,最坏的执行时间就是处理所有规模为n的数据所需要的最长执行时间.之所以关注算法的最坏情况,是因为它通常是最容易分析的情况.此外,它还能够说明程序在各种场景下到底会有多慢.更正式地说,如果Sn是所有规模为n的问题样本si构成的集合,t()代表算法对于每一个问题样本所需要的执行时间,那么算法在最坏情况下的执行时间为:t(si)对于所有si∈Sn的最大值.我们将

2.4 性能指标 在比较算法时,我们使用了问题数据的规模n来评估算法的性能.这是过去半个世纪算法比较的标准方法.通过输入数据的规模评估算法的执行时间,我们可以知晓哪种算法能够更好地适应一些异常规模的问题.性能评估的第二种方法是考虑算法将会耗费多少内存或者存储空间.之后的小节详细讨论这个问题.常见的算法分类(按照效率降序排列)如下:常数级:O(1)对数级:O(log n)次线性级:O(nd),其中d < 1线性级:O(n)线性对数级:O(n log n)平方级: O(n2)指数级:O(2n)注意:

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