《算法技术手册》一2.4.3 次线性级算法O(nd)(d<1)的性能

1.3.1 贪心算法 以下的贪心算法展示了如何找到凸包上的每个点: 1. 删除P中的最低点low--low必须在凸包上. 2. 垂直画一条穿过点low的直线,将剩余的n-1个点分别和点low连线,以垂直直线右侧的点的夹角为正值降序排列,夹角的范围是从90皛-90啊n-2是最右侧的点,而P0是最左侧的点.图1-3中显示了垂直线以及每个点与其的夹角. 3. 以{Pn-2, low, P0}这个顺序组成的点集为基础,在剩余的点中选择可以组成凸包的点--从P1开始,将每个点尝试加至这个点集的尾部,如果

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

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

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

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

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

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

2.3.4 上下界 在本书中,我们简化了"大O"表示法,目的是对不同问题样本在持续增长的规模n下算法性能进行分类.这种分类使用O(f(n))表示,其中f(n)是一些如n.n3或者2n的常见函数.例如,假设存在一个算法,当输入数据规模"足够大"时,它在最坏情况下的性能绝不大于和输入问题样本规模成比例的某个值.更加精确地说,对于所有的n > n0,存在某个常数c > 0,满足t(n) ≤ cn ,其中n0是每个问题样本"足够大时"的基本点

2.4.1 常数级算法的性能 在分析算法性能时,本书常常会强调原生操作都具有常数级的性能.很明显,这个声明并不能完全准确地描述实际操作的性能,因为它没有考虑到硬件问题.例如,比较两个32 位的数x和y的大小,这个操作耗费的时间与x.y的大小无关.常数级的操作被认为具有O(1)的性能.那么在比较两个256 位的数字时,性能又如何呢?比较两个1024位的数字又如何呢?我们认为,在长度k固定的前提下,比较两个k位数字的操作可以在常数时间内完成.这么认为的前提是问题的规模(即x.y的值)不得超过k.由k