《算法技术手册》一导读-阿里云开发者社区

开发者社区> 华章出版社> 正文

《算法技术手册》一导读

简介: Fortune算法,它用于计算点集的Voronoi图。 归并排序,既包括针对内存数据的内部排序,也包括外部文件的外部排序。

2017_09_20_132934

前言

修订一本书向来都是一项艰巨的任务。我们既希望保留第1版(于2009年出版)中的精华,也希望弥补其中的一些不足并增加一些新的篇幅。在第2版中,我们延续了第1版中列出的原则,包括:
使用实际代码而非伪代码来描述算法。
将算法独立于解决的问题之外。
恰到好处地介绍数学知识。
以经验主导支撑数学分析。
在更新修订过程中,我们精简了文字描述,简化了一些布局,从而有助于补充新的算法和其他内容。我们相信,从概括的角度介绍计算机科学的一个重要领域,会对实用软件系统有着深远影响。
第2版的变动
在修订过程中,我们遵循以下原则:
挑选新的算法
在第1版出版之后,我们常常会收到一些留言,比如,“为什么漏掉了归并排序?”或“为什么没有介绍快速傅里叶变换(Fast Fourier Transform,FFT)?”虽然我们无法满足所有这些要求,但第2版还是增添了一些新的算法,包括:
Fortune算法,它用于计算点集的Voronoi图。
归并排序,既包括针对内存数据的内部排序,也包括外部文件的外部排序。
多线程快速排序。
AVL平衡二叉树实现。
新的章节(第10章)用于介绍空间算法,包括R树(R-Tree)和四叉树(Quadtree)。
总的来说,本书差不多介绍了40种核心算法。
简化描述
为了方便新增内容,我们几乎对第1版的所有内容进行了修订,简化了算法描述框架,并且减少了一些附带描述。
增加Python实现
我们并没有使用Python重新实现已有的算法,而是特意为大部分新增的算法提供了Python实现。
管理代码资源
第1版中的代码是通过ZIP压缩包文件的方式提供的。之后,我们就迁移到了GitHub代码库。这些年里,我们不仅提高了代码质量和增加了相关文档,还加入了在第1版出版后撰写的一些博客文章。代码库中不仅拥有超过500个的单元测试用例,还使用代码覆盖工具以确保99%的Java代码都被覆盖。目前代码库中的代码行数总计超过11万行。
目标读者
我们期望这本书能够成为读者的一本主要参考书,方便查阅如何实现和使用某些算法。书中了介绍了一系列用于解决问题的已有算法,并遵循以下的一些原则:
在介绍每种算法时,我们会使用一种固定格式的模板。这种模板可以帮助恰当地设计每一次的讨论和解释每种算法的要点。
我们使用了不同的语言实现了每种算法(包括C、C++、Java和Python)。得益于此,我们能够使用读者熟悉的编程语言对算法进行详细的讨论。
我们描述了每种算法的预期性能,并根据经验加以证明。
我们希望这本书对软件工程师、程序员以及设计师有所帮助。为了实现目标,你需要使用大量关于实际解决方案和算法的资源,才能解决手头的实际问题。你已经知道了如何使用多种语言编写一个程序,也了解了计算机科学中的关键数据结构(例如数组、链表、栈、队列、散列表、二叉树以及有向图和无向图),但是你并不需要亲自实现这些数据结构,因为可以在代码库中找到它们。
我们希望,读者能从这本书中学习到如何选择和测试解决方案来快速高效地解决问题,同时也能学习到一些高级数据结构和使用标准数据结构的新方法来提高程序的性能。而解决问题的能力高低就取决于所选择算法的效率高低。
本书体例
在印刷上的一些例行惯例:
代码(Code)
所有代码示例都使用这种字体。
这些代码都是直接取自代码库,是现实中使用的代码。此外,书中所有代码清单都进行了“美化处理”以强调对应程序设计语言的语法。
斜体(Italic)
斜体用于表示描述算法和数据结构的关键术语,也会用于指代示例伪代码描述中的变量。
等宽字体(Constant Width)
等宽字体用于表示程序实现中的实际软件元素,例如Java 类、C语言实现中的数组名以及常量(如true或false)。
在本书中,我们引用了大量的书籍、文章和网址。这些引用都用括号标注出来,例如(Cormen等,2009),并且在每章末尾都会列出本章所使用的参考文献。若参考引用紧跟在作者姓名之后,则不会重复其姓名。例如,当提到Donald Knuth的《Art of Computer Programming》一书时,括号中仅附带出版年份。
本书中的所有URL于2016年1月验证过,并且我们所选用的URL在近期均可用。除此之外,我们也用到了较短的URL,如http://www.oreilly.com,此类URL会直接出现在正文中,也会出现在脚注和每章末尾的参考文献中。
代码使用说明
补充资料(代码示例、练习题等)可以从https://github.com/heineman/algorithms-nutshell-2ed下载。
本书的目的是帮助读者更好地完成工作。通常来说,你可以在自己的程序和文档中直接使用本书提供的示例代码。除非需要大量复制这些代码,否则你不需要联系我们获得许可。例如,如果你所编写的程序使用了本书中几段代码,则无须获取许可。但是如果作销售或者发行光盘之用,则需要许可。引用本书和使用书中的样例代码回答问题也无须获取许可。但是如果你在自己的产品文档大量地使用本书中的代码,则需要许可。
我们希望但是不强制要求标明归属。一个归属说明通常包括标题、作者、出版商和ISBN 。例如,“George T. Heineman、Gary Pollice 和Stanley Selkow 编写的《Algorithms in a Nutshell, Second Edition》。C2016 George Heineman、Gary Pollice and Stanley Selkow,978-1-4919-4892-7。”

目录

1.1 理解问题
1.2 简单解法
1.3 高明做法
1.3.1 贪心算法
1.3.2 分治算法
1.3.3 并行算法
1.3.4 近似算法
1.3.5 融会贯通
1.4 总结
1.5 参考文献
第2章 算法的数学原理
2.1 问题样本的规模
2.2 函数的增长率
2.3 最好、最坏和平均情况下的性能分析
2.3.1 最坏情况
2.3.2 平均情况
2.3.3最好情况
2.3.4 上下界
2.4 性能指标
2.4.1 常数级算法的性能
2.4.2 对数级算法的性能
2.4.3 次线性级算法O(nd)(d<1)的性能
2.4.4 线性算法的性能
2.4.5 线性对数算法的性能
2.4.6 二次方的算法性能
2.4.7 性能不明显的计算
2.4.8 指数级算法性能
2.4.9 渐进增长小结
2.5 基准测试
2.6 参考文献
第3章 算法基础
3.1 算法模板的格式
3.2 伪代码模板的格式
3.3 实验评估的格式
3.4 浮点计算
3.4.1 性能
3.4.2 舍入误差
3.4.3 浮点值的比较
3.4.4 特殊值
3.5 算法举例
3.5.1 算法名称和摘要
3.5.2 输入/输出
3.5.3 使用环境
3.5.4 解决方案
3.5.5 算法分析
3.6 常用方法
3.6.1 贪心
3.6.2 分治
3.6.3 动态规划
3.7 参考文献

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接