《算法技术手册》一第2章 算法的数学原理

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

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

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

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

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

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

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

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