编程语言只是“工具”，算法才是“灵魂”。想要在程序猿道路上走得更长远，想要成为优秀的算法攻城狮，算法就是必须要掌握的“内功“。

随着算法岗应聘人数剧增，大厂的要求也随之提高。很多大厂面试的时候都喜欢考察算法的相关知识和手撕代码的能力。有很多人代码能力过硬，但每次面试都会在算法上给跪了……

所以想要顺利进入大厂，千万别让 算法 拖了你的后腿。大厂在校招的时候钟爱考察算法知识，通常是因为面试的学生项目经验少，只能考察算法基础知识。社招就更加残酷，越厉害的大厂越注重考察算法。相比较短期的代码能力，他们更看中你的长期潜力（算法设计能力）。掌握每个攻城狮都必知必会的算法设计技术，轻松“跃龙门”成为一名优秀的大厂攻城狮。

算法设计

￥57.1

购买

1、必知必会的算法设计技术

• 算法是什么？

算法是指解题方案的准确而完整地描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。

算法即是能够对一定规范的输入，在有限时间内获得所要求的输出。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

理论定义有些晦涩难懂，但是异步君想告诉大家其实算法无处不在，生活中处处都有着算法的“身影”，如居民缴电费也是个简易算法逻辑问题。

• 算法的特征是什么？

以下是高德纳在他的著作 《计算机程序设计艺术》 里对算法的特征归纳：

• 算法设计的要求是什么？

设计一个算法必须满足的四大特点：

• 常用的算法设计技术

贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最有利的选择，从而希望导致结果是最好的算法。 贪心算法总是能做出 当下最好的选择 ，但因为容易 过早做决定 所以 无法 得到最优解。

基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完。 贪心算法可以应用于 背包问题 、 单源最短路径 、 哈夫曼编码等。

贪心算法步骤如下所示：

分治法

分治算法就是把一个复杂的问题分成两个或多个相同的子问题，直到可以对最终的子问题直接求解。 最终原问题的解即是子问题解的合并。对于一个规模为m的问题，将其分解为n个规模较小的子问题。这些子问题互相独立且与原问题形式相同，递归地求解这些子问题后将各个子问题的解合并得到原问题的解。 分治法可以应用于 二分搜索、排序算法、傅立叶变换等。

分治算法步骤如下所示：

动态规划

动态规划适用于 最优子结构性质 和 子问题重叠性质 的问题 。 最优子结构性质是指如果问题的最优解所包含的子问题的解也是最优的。最优子结构是 局部最优解能决定全局最优解 ，换而言之，问题能够分解成子问题来解决。

另外子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。为避免多次解决相同子问题，结果被保存直到从简单的问题到整个问题都被解决。因此， 动态规划保存递归的结果使得在解决同样的问题时不会花费时间 。 动态规划法可以应用于 0-1背包问题 、 最长公共子序列 、 斐波那契数列等。

动态规划步骤如下所示：

回溯法

回溯法是一种选优搜索法，按选优条件向前搜索达到目标。 回溯法尝试分步解决一个问题，当探索到某一步时，发现原先选择并不优，就退回一步重新选择，这种即为回溯法。其中满足回溯条件的某个状态的点称为回溯点。回溯法通常用最简单的递归方法来实现 回溯法可以应用于八皇后问题 、0-1背包问题。

回溯法步骤如下所示：

分支限界法

分支限界法常以广度优先或最大效益优先的方式搜索问题的解空间树。分支限界法的基本思想是对有约束条件的最优化问题的所有可行解空间进行搜索。

该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解的值计算一个上界或下界。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出可行解为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得最优解。将问题分枝为子问题并对这些子问题定界的步骤称为分支限界法。

分支限界法可以应用于 旅行商问题、选址问题、背包问题

分支限界法步骤如下所示：

学习算法设计理论基础知识是必要的，但 更重要的 是掌握算法设计思路 。如何 在不同计算领域的 复杂问题 中识别算法问题的 清晰描述形式 ，并针对由此产生的问题 设计有效的算法 成为学习算法设计技术过程中的 重中之重 。

有这样一本算法书，着重对算法设计思维的培养，畅销15年，豆瓣原版9.0分，口碑与质量绝佳，更值得一提的是，这本书还是哈佛、斯坦福、普林斯顿、多伦多等多所知名高校选用的算法教材。这本书就是 康奈尔大神Kleinberg的经典教材《算法设计》（Algorithm Design） ，一本最适合入门的经典算法书！

2、好书推荐

《算法设计》

作者： [美] 乔恩•克莱因伯格（Jon Kleinberg） 伊娃•塔多斯（Éva Tardos）

《算法设计》讲了什么？

本书围绕算法设计进行组织，对每种算法技术用多个典型范例进行分析，把算法的理论跟实际问题结合起来，具有很大的启发性。本书 侧重算法设计思路 ，每章都从实际问题出发，经过深入具体的分析引出相应算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面广，且含有 200多道精彩的习题，最后还扩展了PSPACE问题、参数复杂性等内容。

这本书有什么独到之处？

《算法设计》和其他算法书最大的区别在于注重 算法设计思维 的培养，每一章都从实际问题出发，通过分析真实世界的问题来激发算法思想，将算法设计思维带入算法研究中。

本书利用了许多计算机科学和相关领域的问题来开发基本的算法设计技术。这里列出一些有代表性的例子，相当详细地讨论了来自下列领域的应用，包括 系统和网络的应用程序(缓存、交换、互联网上的域间路由)，人工智能(规划、博弈、霍普菲尔德网络)，计算机视觉(图像分割)，数据挖掘(变更点检测、聚类)，运筹学(航线调度)，以及计算生物学(序列比对、RNA 二级结构) 。

计算难解性的概念，特别是NP完全性，在本书中起着重要作用。有时，在应用领域出现的有趣问题存在有效的解决方案，而有时候它可以被证明是NP完全的。为了全面考察新的算法问题，人们应该能够同样熟练地探索这两个方面。由于计算机科学中的许多自然问题都是 NP 完全的，因此开发处理难解问题的方法已成为算法研究中的一个关键问题。不应将发现问题是 NP 完全的看作故事的结束，而应该将其看作是对我们开始寻找近似算法、启发式局部搜索技术或易解的特殊情况的鼓励。

问题和带解答的练习

大多数书籍都具有相当多的练习题以及问题，但都缺少解答或者解答得不全面，本书的“带解答练习”完美地解决了这个问题。

本书共包含200个问题，几乎都是在康奈尔大学算法课程的课外作业中被开发，或者课堂测验的考试题目，其中部分题目出自Yahoo!和Oracle等公司。

“带解答的练习”部分讨论一个或多个问题，并描述如何形式化一个解，包括 带完整解释的算法、运行时间的分析和正确性的证明 。

教学特色和补充材料

除问题和带解答的练习之外，本书还有一些其他教学特色和补充材料，以方便教学。如前所述，本书中大量篇幅专门用于算法问题的形式描述，以及针对该问题的算法设计和分析。为了反映这种风格，这些部分始终围绕一系列小节进行组织：

• “问题”描述问题并确定精确的形式定义
• “设计算法”采用适当的设计技术开发算法
• “分析算法” 证明算法的性质并分析它的效率

本书可以提供由普林斯顿大学的 Kevin Wayne 开发的一套教学用 PPT，它是按照本书章节的顺序组织的，可以作为以本书为教材的课堂教学的材料。这些文件可在培生教育出版集团的官方网站上获得（需要教师申请）。

读完这本书你可以学会什么？

1、学习图的基本定义、图的遍历技术(如宽度优先搜索和深度优先搜索)、有向图概念(包括强连通性和拓扑排序)以及基本数据结构。

2、学习 4 种主要的算法设计技术： 贪心算法、分治法、动态规划和网络流 。

• 对于贪心算法，读者可以学习到在何种情况下使用贪心算法最好。贪心算法主要应用，包括最短路径、无向生成树和有向生成树以及聚类和压缩。
• 对于分治法，读者学习到如何将递推关系求解为运行时间的界限。然后，对这些递推的熟悉程度指导算法的设计，这些算法改进了对许多基本问题的直接方法，包括排名比较、平面上最近点对的计算，以及快速傅里叶变换。
• 对于动态规划，读者学习到如何从隐藏在它背后的递归直觉开始，然后通过它们自然产生的应用，构建越来越多有表现力的递推形式描述。
• 对于网络流问题的算法，读者学习到网络流的大量不同应用，通过在负载均衡、调度、图像分割和许多其他问题中的应用，学习到它的多种能力。

3、对于NP 完全问题，读者学习到在遇到新问题时识别用于归约的候选项，构建有难度的归约。学习NP 完全性之外的计算难度类型，特别是 PSPACE 完全性。即强调难以解决的问题并非以 NP 完全性为终点，而 PSPACE 完全性也构成了人工智能的一些核心概念的基础(规划和博弈游戏)，否则无法在考察的算法世界中找到它们的位置。

4、读者学习处理计算难解问题的3种主要技术，即 识别结构上的特殊情况、近似算法和局部搜索启发式算法。

• 学习特殊情况，当 NP 完全问题仅限于树结构输入时，学习如何有效地解决。
• 学习近似算法，设计有效算法的过程和充分理解最优解，以明白算法的界限。
• 学习局部搜索启发式算法，包括 Metropolis 算法和模拟退火算法。

本书适合哪些读者？

本书适合作为计算机及相近专业本科高年级学生以及研究生算法课程的参考教材，也适合作为对信息学奥林匹克竞赛感兴趣的高中生的指导书籍。对算法分析和设计感兴趣的IT专业技术人员也可以将本书作为案头必备的参考书或工程实践手册。