专栏名称: 人工智能头条

专注人工智能技术前沿、实战技巧及大牛心得。

十年磨一剑，这是一本有声音的算法书

人工智能头条 · 公众号 · AI · 2019-01-11 19:11

正文

不要错过文末留言活动

这本书在美亚评分4.7，在作者的 在线算法课程 的基础之上编写的，是四卷本系列的第1卷。

这个在线课程2012年起就定期更新，它建立在作者在斯坦福大学教授多年的本科课程的基础之上。也许你有所耳闻， 这本书就是《算法详解（卷1）——算法基础》。如果你更喜欢听和看，可以在 YouTobe 上搜索这本书的主题课程，免费观看。

YouTube 课程图

《算法详解（卷1）——算法基础》作者蒂姆·拉夫加登（Tim Roughgarden）是斯坦福大学计算机科学系的教授,也是该校管理科学和工程系的客座教授，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第一卷。

这本书详细讲解算法基础，展现算法本质 ,是一本囊括基本算法知识的详解指南。集斯坦福大学教授多年教学经验，深入浅出，通俗易懂。

《算法详解（卷1）——算法基础》

作者：[美] 科里•奥尔索夫（Cory Althoff）

扫描二维码，一键购买

这本书讲什么？

本书对以下4个主题进行了介绍。

渐进性分析和大O表示法

渐进性表示法为讨论算法的设计和分析提供了基本术语。它的关键概念是大O表示法，这是一种用于衡量算法的运行时间粒度的建模选择。

我们将会看到，清晰的高层算法设计思想的一大优点就是可以忽略常数因子和低阶项，把注意力集中在算法的性能与输入长度之间的关系上

分治算法和主方法

算法设计中不存在万能的捷径，不存在适用于所有的计算问题的一种解决问题的方法。但是，还是存在一些通用的算法设计技巧适用于一定范围内的不同领域。在本系列的第1卷中，我们将讨论“分治”技巧。

分治法的思路是把一个问题分解为几个更小的子问题，然后递归地解决这些子问题，并把它们的解决方案快速组合在一起形成原始问题的解决方案。

我们将讨论用于排序、整数乘法、矩阵乘法和基本的计算几何学问题的快速分治算法。我们还将讨论主方法，它是一个强大的工具，用于分析分治算法的运行时间。

随机化算法

随机化算法在运行时采用了“掷硬币”的方式，它的行为取决于掷硬币的结果。令人吃惊的是，随机化常常能够带来简单、优雅且实用的算法。

其中一个经典例子是随机化的快速排序（QuickSort）算法，我们将详细介绍这个算法并分析其运行时间。我们还将在《算法详解》系列的第2卷看到随机化算法的进一步应用。

排序和选择

作为前3个主题研究的附加成果，我们将学习几个著名的排序和选择算法，包括归并排序（MergeSort）、快速排序和线性时间级的选择（包括随机化版本和确定性版本）。

这些算法具有令人炫目的高速度，以至于它们的运行时间较之读取输入所需要的时间并没有多出很多。

创建类似这样的“低代价基本操作”集合，既可以直接用它来操作数据，也可以将其作为更困难问题的解决方案的基本单位。

关于本书内容的更详细介绍，可以阅读每章的“本章要点”，它对每一章的内容进行了总结，特别是那些重要的概念。

《算法详解》系列其他几卷所涵盖的主题

《算法详解（卷2）》讨论了数据结构（堆、平衡搜索树、散列表、布隆过滤器）、图形基本单元（宽度和深度优先的搜索、连通性、最短路径）以及它们的应用（从消除重复到社交网络分析）。

卷3重点讨论了贪婪算法（调度、最小生成树、集群、霍夫曼编码）和动态编程（背包、序列对齐、最短路径、最佳搜索树等）。

卷4则介绍了NP完整性及其对算法设计师的意义，还讨论了处理难解的计算问题的一些策略，包括对试探法和局部搜索的分析。

本书经常会出现“Q.e.d”等字样，它是quod erat demonstrandum的缩写，表示“证明完毕”。在数学著作中，它出现在证明过程的最后，表示证明已经完成。

学好算法你将收获什么？

精通算法需要大量的时间和精力，那为什么要学习算法呢？

成为更优秀的程序员

读者将学习一些令人炫目的用于处理数据的高速子程序以及一些实用的数据结构，它们用于组织数据，并可以直接部署到自己的程序中。

实现和使用这些算法将会扩展并提高读者的编程技巧。读者还将学习基本的算法设计范式，它们与许多不同领域的不同问题密切相关，并且可以作为预测算法性能的工具。这些“算法设计模式”可以帮助读者为自己碰到的问题设计新算法。

加强分析技巧

读者将会获得大量的实践以对算法进行描述和推导。通过数学分析，读者将对《算法详解》系列图书所涵盖的特定算法和数据结构产生深刻的理解。读者还将掌握一些广泛用于算法分析的实用数学技巧。

形成算法思维

在学习了算法之后，很难发现有什么地方没有它们的踪影。不管是坐电梯、观察鸟群，还是管理自己的投资组合，甚至是观察婴儿的认知，算法思维都如影随行。算法思维在计算机科学之外的领域，包括生物学、统计学和经济学越来越实用。

融入计算机科学家的圈子

研究算法就像是观看计算机科学最近60年的精彩剪辑。当读者参加一个计算机科学的鸡尾酒会时，会上有人讲了一个关于 Dijkstra 算法的笑话时，你就不会感觉自己被排除在这个圈子之外了。在阅读了本书系列之后，读者将会了解许多这方面的知识。

在技术访谈中脱颖而出

在过去这些年里，有很多学生向我讲述了《算法详解》系列图书是怎样帮助他们在技术访谈中大放异彩。

这本书里有什么资源？

《算法详解》系列的在线课程当前运行于Coursera和Stanford Lagunita平台。另外还有一些资源可以帮助读者根据自己的心愿提升对在线课程的体验。

视频。 如果你觉得相比阅读文字，更喜欢听和看，那么可以在YouTube的视频播放列表中观看。这些视频涵盖了《算法详解》系列的所有主题。我希望它们能够激发读者学习算法的持续热情。当然，它们并不能完全取代书的作用。

小测验。 你怎么才能知道自己是否完全理解了本书所讨论的概念呢？散布于全书的小测验及其答案和详细解释就起到了这个作用。当读者阅读到这块内容时，最好能够停下来认真思考，然后再继续阅读接下来的内容。

章末习题 。每章的末尾都有一些相对简单的问题，用于测试读者对该章内容的理解。另外还有一些开放性的、难度更大的挑战题。本书并未包含章末习题的答案，但是读者可以通过本书的论坛（稍后介绍）与我以及其他读者进行交流。

编程题。 许多章的最后部分是一个建议的编程项目，其目的是通过创建自己的算法工作程序，来培养读者对算法的完全理解。读者可以在www.algorithmsi- lluminated.org上找到数据集、测试例以及它们的答案。

论坛。 在线课程能够取得成功的一个重要原因是它们为参与者提供了互相帮助的机会，读者可以通过论坛讨论课程材料和调试程序。本书系列的读者也有同样的机会，你可以通过www.algorithmsilluminated.org参与互动。

第1章绪论 1

1.1 为什么要学习算法 1

1.2 整数乘法 3

1.2.1 问题和解决方案 3

1.2.2 整数乘法问题 3

1.2.3 小学算法 4

1.2.4 操作数量的分析 5

1.2.5 还能做得更好吗 5

1.3 Karatsuba乘法 6

1.3.1 一个具体的例子 6

1.3.2 一种递归算法 7

1.3.3 Karatsuba乘法 9

1.4 MergeSort算法 11

1.4.1 推动力 11

1.4.2 排序 12

1.4.3 一个例子 13

1.4.4 伪码 14

1.4.5 Merge子程序 15

1.5 MergeSort算法分析 16

1.5.1 Merge的运行时间 17

1.5.2 MergeSort的运行时间 18

1.5.3 定理1.2的证明 19

1.5.4 小测验1.1～1.2的答案 23

1.6 算法分析的指导原则 23

1.6.1 第1个原则：最坏情况分析 24

1.6.2 第2个原则：全局分析 25

1.6.3 第3个原则：渐进性分析 26

1.6.4 什么是“快速”算法 27

1.7 本章要点 28

1.8 习题 29

挑战题 31

编程题 31

第2章渐进性表示法 32

2.1 要旨 32

2.1.1 推动力 32

2.1.2 高级思维 33

2.1.3 4个例子 34

2.1.4 小测验2.1～2.4的答案 38

十年磨一剑，这是一本有声音的算法书

正文

请到「今天看啥」查看全文