《算法技术手册》一1.3.2 分治算法

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

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

3.5.1 算法名称和摘要 Graham扫描算法可以计算出笛卡儿空间给定点集的凸包.它首先会寻找输入集P中的最低点low,然后将剩下的点{P-low}按照和low的极角从大到小排序.之后算法会按序遍历这些点构建凸包,如果凸包上最新的三个点构成一个左拐,那么最新加入的点就需要被删除掉.

3.6.2 分治 分治通常是将一个规模为n的问题划分成两个独立的子问题,其中每个子问题的规模约为n/2.大部分时候分治策略是递归形式的,并且会有简单易懂的基本条件用于结束递归.此外,在计算出两个较小问题的解之后,还必须要有一些计算来根据子问题的解计算出原问题的解.下面来看一个例子:求包含n个数的数组中的最大元素.例3-2展示了如何将原问题分解成两个子问题并通过递归求解.通常,最大值一般是两个子集各自的最大值中比较大的那一个.仔细观察尾递归触发的条件,即子集中只有一个元素vals[left]返回.

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

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

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

1.3.5 融会贯通 通常,解决某一类问题的算法和解决某一个特定问题的算法是大致相通的.Voronoi图(Preparata and Shamos,1993)是这样一个几何结构--它可以将平面上的点集划分成多个区域,其中每个区域的重心点为输入集P中的点.每个区域Ri中任意一点(x, y)到Pi的距离都比到其他区域的重心点要近.图1-7展示了计算出的Voronoi图.灰色区域是半无限的,并且灰色区域的重心点组成了凸包.由此可以得出以下算法: 1. 计算输入集P的Voronoi图. 2. 将P中的最

2.4.6 二次方的算法性能 现在考虑一个类似的问题:两个n位的整数相乘.例2-4展示了使用小学课堂上学过的算法实现的乘法运算,其中n位数字的表示方法与之前的加法一样. 例2-4:mult乘法的Java实现 public static void mult (int[] n1, int[] n2, int[] result) { int pos = result.length-1; // 清除所有的值 for (int i = 0; i < result.length; i++) { result