C语言而已“辅助工具”，演算法才是“肉体”。想在流程猿高架道路上走得更长远规划，想正式成为杰出的演算法守城狮，演算法是要要掌控的“心法“。

随著演算法岗应征数目激增，小厂的明确要求也骤然提升。许多小厂复试的这时候都讨厌实地考察演算法的有关科学知识和手撕标识符的潜能。有许多人标识符潜能优良，但每天复试单厢在演算法上给跪了……

因此想成功步入小厂，可别让演算法拖了你的大树枝。小厂高二招的这时候偏爱实地考察演算法科学知识，一般来说原因在于复试的小学生工程项目实战经验少，根本无法实地考察演算法基础科学知识。社招就更为残暴，越吓人的小厂越著重实地考察演算法。相比较中长年的标识符潜能，她们更看上你的长年发展潜力（演算法结构设计潜能）。掌控每一守城狮都乌兹县必会的演算法结构设计控制技术，随心所欲“紫脉”正式成为一位杰出的小厂守城狮。

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种主要控制技术，即识别结构上的特殊情况、近似演算法和局部搜索启发式演算法。

本书适合哪些读者？

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