如何设计算法(2018)

如果您错过了我的前一篇文章，我将花一系列文章在我审核Steven Skiena的CSE373算法分析类时提供注释。

在第一堂课中，Skiena提到在学习本材料之前，您应该先修一门数据结构课程和一门线性代数课程。

出于专业(阅读：实用)的目的，我们显然不是从零开始，但在教学大纲中达到顶峰我相信我们可以通过用JavaScript实现数据结构(毕竟，这是一个前端博客)来合并数据结构。

尽管基础线性代数会有所帮助，但在技术面试中，无论如何都不会有任何东西值得深入研究，所以我们可以放心地跳过这一先决条件。

算法是一个指令集。有点像菜谱。就像你在一些随机博客上找到的花椰菜米饭食谱一样，你可以把它翻译成你想要的任何语言。

算法也是如此：它们是语言不可知的，可以用人类可读的形式或机器可读的形式来表示。想法越简单，用英语表达就越容易。算法越复杂或越细微，您就越有可能依赖机器语言，如Python或JavaScript。

出于实际目的，可以将算法的高级概述看作是在潜入代码之前用英语向面试官解释的内容，但要明白，为了证明您作为程序员的能力，代码必须是解释和验证您设计的算法的主要来源。

将算法与其他指令分开的算法的两个定义特征是：

这是正确的。有没有人因为在技术面试中实现了一种算法而每次都没有产生正确的结果而受到表扬？

这很有效率。我们希望我们的算法在我们变老之前的某个时候运行。

现在，从技术上讲，程序不一定要正确运行才能被接受。运行大部分正确指令的程序称为试探法。这些将在以后学习近似算法时变得重要，但是现在，假设正确性是一个要求。

校样不是我在高中或大学的强项。出于某种原因，我从来没有真正理解过这一点，因为证明中的步骤似乎从来不符合我的大脑过去从一个步骤跳到下一个步骤的逻辑。

幸运的是，证明正确最简单的方法就是证明某事不正确。

当我们试图找出一个正确有效的算法来解决问题时，我们可以通过剔除那些不正确的算法来缩小可能的选择范围。反例证明比其他方法容易得多。

作为一个简单的例子，假设我们有一个总数T=6，我们想要通过将数字相加到一个有效的集合(如S=[1，2，3])来争取。看起来解决这个问题的一个非常简单的算法是从左到右挑选数字，直到我们达到总和T。即使您在开始时添加一个大数字，如S=[5，1，2，3]，这也是可行的，因为我们可以只删除最后两个数字。

首先，我们选择5，它小于6。在我们的集合中，在已经选择5之后，没有其他数字可以加起来等于6，但是仍然有一个有效的配置可以满足T(2和4)。这是通过反例证明我们的算法是不正确的。这也是一个非常简单的反例。反例在现实世界中很有用，可以帮助您快速评估您所走的道路是好的还是不好的。

如果您能想出一个相对简单的反例(简单的意思是它应该只需要几个变量或项)，那么您就知道您的算法在到达时就失效了，您需要尝试其他方法。如果您做不到，那么您很可能是在正确的轨道上，但这并不意味着您的算法一定是正确的。

证明正确性的一种方法是归纳法。归纳法证明表明，如果我们能解决n+1的基本情况和一般情况，我们就知道我们已经为所有可能的输入提供了正确的答案。

关于归纳，这里有两个重要的联系，这两个联系在专业环境中很有用：

归纳法证明是递归的一种数学形式。递归是编程中的一个基本概念，它允许函数调用自身。它允许我们把大问题分成小问题。

这里的经典例子是斐波那契数列(一个整数序列，其中当前数是前两个数的和)。要为序列中的值n计算斐波纳契数，您可以为每个n的输入手动计数前面的所有数字，但这不仅既慢又费力，而且很难用程序来表示。

另一种方法是对几种基本情况(n=0和n=1)进行计数，以开始计数，然后使用上一步的总和值连续调用Fibonacci函数。递归允许我们在代码中实现这一点。它是处理归纳的编程策略，这是验证对我们的数据集进行操作的算法的语句的数学策略。

归纳法证明对求和很有用。如果你把很多输入加在一起，你需要证明它对所有情况都有效，即使是比你定义的集合更大的情况，也可以用归纳法来证明。

但是，你需要在工作或面试中正式证明什么吗？绝对不行。但是您将需要测试您的代码，而测试是一种证明形式。

因此，虽然正式的归纳数学证明可能比你在专业设置中展示的任何时候都要严格得多，但它确实定下了基调，你不能简单地编写代码，让人们假设你写的是正确的。它需要以某种方式进行测试，因此，如果您有这样一种心态，即您的算法需要以某种形式证明是正确的，那么您就走上了编写高质量代码的正确道路。

如果我们将主要使用代码来表示我们的算法，并通过测试来证明它们的正确性，那么大O符号将被用来证明我们的算法是有效的。

我们将在本系列后面的一篇文章中介绍Big O，但现在要记住的重要一点是，一般来说，您会希望争取在大数据上花费合理的时间。

例如，如果您设计的东西需要n！时间的阶乘，任何超过微不足道的30个项目，你处理的数字都大于已知宇宙中的恒星数量。你可能想要跑得比那快一点的东西。

大多数CS课程(和大多数学校)只关心这两件事。如果你的老师和助教能在合理的时间内成功地运行你的程序，你就会得到A。现实生活不会在这两件事上给你A，因为你不会像在习题集或考试中那样在真空中学习。那么，现实世界的图景中缺少了哪些东西呢？

正交性：您的代码依赖于其他东西吗？您是在编写状态代码还是函数代码？由于大多数编码白板问题都是孤立的和自包含的，您通常不能对此进行测试，因此请确保您提供了一个真实项目和开放源代码的组合来演示这一点。

可读性：您可以编写最破解的代码来使算法工作，但在现实世界中，其他人不能阅读或使用该代码，这是失败的。确保您有时间，并且您的代码是正确和高效的，进行重构以证明您可以编写可读的、可重用的代码，这些代码是干的(不要重复自己)和正交的(或者至少可以作为正交系统的一部分来编写)。

现在我们知道了什么定义了算法，需要什么来证明它值得用来解决我们的问题，下一步就是决定我们将如何设计我们的算法。对问题建模意味着了解您正在处理的对象，我们将介绍两类对象：

组合对象只是一种奇特的表达方式，意思是“我可以用什么东西来计数？”因为机器只是大的0和1工厂，组合对象是我们收集和组织机器每秒执行数十亿条指令的所有0和1数学的方式。我们在谈论什么样的事情呢？

排列：集合的重新排序。这方面的口语化术语包括安排、游览、订购和/或顺序之类的词。

字符串：字符或图案的序列。可以把字符串想像成排列，但使用字母而不是数字。文本、字符、模式、标签、句子等词是您处理字符串数据的关键见解。

子集：集合的一部分。如果您看到诸如cluster、Collection、Committee、group、Packaging或Selection之类的词，那么您可能已经有了一个子集。

点：空间中的位置。节点、站点、位置、记录或位置等词都是对点的引用。

图形：带有顶点的节点连接它们并为它们指明方向。我们在本文前面已经提到过这一点。网络、电路、网络和关系等词都用来描述图形。

树：向一个方向流动并且不在开始处结束的图形(非循环)。当它们完全平衡时，它们看起来就像一棵圣诞树。诸如层次结构、优势关系、祖先/后代关系、分类等词都是您在问题中处理树的指示器。

多边形：在同一位置(循环)开始和结束的图形，表示物理空间中的形状或区域。其他单词，如配置和边界，都表明您的问题陈述可能是在处理多边形。

递归对象与上面的组合对象不同，它只获取可计数的内容，并询问“当您删除其中一个内容时会发生什么？”

换句话说，如果从集合中删除1个项目，则会产生较小的排列集合。

字符串也是如此：只要删除一个字母，就会得到一个较小的字符串。

子集本质上是递归的，因为通过删除一个对象，该对象本身就是一个子集。

有了一组点，用一条线将这些点向下拆分，现在您就有了两个较小的点集。(同样适用于多边形)。

从树中删除一个节点只是一个较小的树。你知道…的想法了吗。

对于递归对象，基本情况始终是空的或单独的集(如果是多边形，则为三角形)。

有了我们可以支配的上述对象，我们就有了所有必要的工具来开始将我们的问题映射到真实的对象中，然后我们可以使用我们的算法来处理这些对象。

Skiena在接下来的每堂课中都提供了一个需要思考的问题。这有点像是一道快速练习题，用来测试你是否领会了上一节课的核心思想。在下一堂课开始时，他详细地复习了问题(和解决方案)。所以在两天后的8月30日讲座中，他要解决算法设计手册中的问题1-5。下面是它看起来的样子：

背包问题如下：给定一组整数S={S1，S2，.。。。，sn}和目标数T，找到S的子集，其加起来恰好为T。例如，在S={1，2，5，9，10}内存在加起来为T=22但不是T=23的子集。

也就是说，在算法没有找到使背包完全装满的解的情况下，即使存在完整的背包解，也要给出S和T。

(A)将S的元素按从左到右的顺序放置在背包中(如果它们合适的话)，即First-Fit算法。

(B)将S的元素从小到大放入背包中，即最佳拟合算法。

我的计划是在讲座之前解决这个问题，在本系列的下一篇文章中提出这个问题，开始这篇文章，看看它是否与课程中给出的答案一致，然后比较和对比不同的方法，并讨论在此过程中出现的任何缺陷或问题。

哇，这可能是我写过的最长的帖子之一。我希望这篇文章能说服你最终一劳永逸地学习数据结构和算法。即使您不专注于学习整个课程，如果您在JavaScript中使用这些内容时可能需要引用或检查本文的某些部分或部分，我也希望这篇文章可以作为参考指南。

注册我们的时事通讯，并获得免费的UI速成课程，帮助您在不需要设计背景的情况下构建漂亮的应用程序。只需在下面输入您的电子邮件，您将立即获得下载链接。