通过 Lisp 语言理解编程算法：简介和复杂度
Lisp 的历史很悠久，早在 1958 年，John McCarthy 就设计了 Lisp 语言，是现今第二悠久而仍广泛使用的高端编程语言。只有 FORTRAN 编程语言比它更早一年。Lisp 一经问世，就站在计算机科学研究的前沿，特别是人工智能的研究方面。现在，它很少被用到，但这一切并不是因为古老，类似古老的语言却被广泛应用。
Lisp（历史上曾拼写为 LISP），是具有悠久历史的计算机编程语言家族，有独特和完全括号的前缀符号表示法。Lisp 编程语族已经演变出许多种方言。现代最著名的通用编程语种是 Clojure、Common Lisp 和 Scheme。
Lisp 最初创建时受到 Alonzo Church 的 lambda 演算的影响，用来作为计算机程序实用的数学表达。因为是早期的高端编程语言之一，它很快成为人工智能研究中最受欢迎的编程语言。
在计算机科学领域，Lisp 开创了许多先驱概念，包括：树结构、自动存储器管理、动态类型、条件表达式、高端函数、递归、自主（self-hosting）编译器、读取﹣求值﹣输出循环（英语：Read-Eval-Print Loop，REPL）。其中一些我们今天已经习以为常，另一些则刚刚在其他高级语言中出现，至今还有 2 种是 Lisp 独有的。可以这样说，直到今天，最高级的主流语言，也只是刚刚接近 Lisp 的水平。虽然已经很接近了，但还是没有 Lisp 那样强大。
本文作者 Vesvolod Dyomkin 正在写一本关于算法和 Lisp 的书。事实上，这件事在几年前就开始了，但这几年来，Vesvolod Dyomkin 一直断断续续地写作，很难抽出大段时间，而且写作时间不多，也没有每天坚持在写。但现在，Vesvolod Dyomkin 终于可以开始出版这本书了。Vesvolod Dyomkin 打算这样做先把这本书的章节发布到博客，然后汇总起来在 Learnpub 上发布最终版：Vesvolod Dyomkin 希望这本书能够在第一批读者的评论下得到改进和润色。本书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。
本书将有 16 章，分为 3 个部分：基本数据结构、衍生数据结构和高级算法。Vesvolod Dyomkin 计划大约每周发布一次，争取在今年底前全部发完。
Vesvolod Dyomkin 希望本书对那些开始从事编程职业生涯或想要提升编程水平的读者们有所启迪。至少，在过去 10 年来，Vesvolod Dyomkin 在生产算法开发、相关课题教学和 Lisp 编程方面积累了大量经验，下面是简短的序言和关于复杂度的绪论。
为什么算法很重要
目前，在我们的行业中，就算法对于程序员工作的重要性来看，普遍存在某种误解。在求职面试中提出的算法问题，与开发者的工作日常之间往往存在脱节。这就是为什么有人会认为，实际上，你不需要精通计算机科学就能在软件开发工作中获得成功。没错，你确实不必懂计算机科学方面的知识。但如果你要成为声名鹊起的前 10% 的程序员，你最好还是要精通计算机科学知识。有几个原因，其中之一是：你几乎可以在工作的每个角落发现算法的影子——只要你意识到算法的存在。简单地说，对于某个特定的编程问题，就算你不知道更有效或更优雅的解决方案，这并不会让代码变得多么槽糕。当前软件开发的趋势是，尽管硬件变得更高效，但软件反而变慢了。以我个人拙见，我认为有两个原因：
大多数应用程序员并不懂底层平台的内部工作原理。而且平台层的数量还在不断增加。
大多数程序员也没有掌握足够的算法和算法开发技术，从而无法最大限度利用他们的代码。如此一来，就会带来一个或多个数量级的性能损失。
在本书中，我将以讨论第二个问题为主，但也会尽可能涉及第一个问题。此外，在日常工作中，学习解决困难算法问题可以训练大脑，让你更容易解决其他问题。
最后，你将会像其他高级程序员一样使用同一种通用语言——超越特定编程语言的世俗差异。届时，你将会对这些差异有一个更超然的看法，让你摆脱思维定势。
产生这种对算法价值的理解差距的原因之一，可能与计算机科学课程中通常是如何讲解算法价值有关。首先，它通常是用一种相当理论化或“数学”的方式进行讲解：有严格的证明，并且与现实世界缺乏联系。其次，受众通常是大学新生或大二学生，他们没有多少实际的编程经验，因此无法理解和联系这些知识如何应用到他们的编程挑战中（因为他们还没有这些经验）——相反，他们中的大多数人仍然停留在努力学好第一门编程语言的水平，并且，他们在对计算的理解上，与选择和特性也有很大关系。
在本书中，重点是演示在计算机编程的各个领域中所描述的数据结构和算法的使用。此外，我预计那些自我选择的读者中，将包括在该领域有一定经验的程序员。这在一组相关课题以及如何表达这些课题方面产生了显著差异。另一个对读者很有帮助的事情是，当程序员精通多种编程语言时，特别是当这些语言来自不同的范式时：静态和动态、面向对象和函数。这些因素可以弥合“理论”算法和实际编码之间的鸿沟，使得这个课题变得易懂、有趣且有启发性。
这是一个可能的问题答案：为什么还要写另一本关于算法的书？事实上，关于这一课题已经有几本不错的教科书和在线课程，其中，我最为推荐的是 Steven Skienna 写的 The Algorithm Design Manual （《算法设计手册》）。然而，正如我所说，这本书在写作方面上没有一丁点儿“学术味儿”，这就是其他教科书的标准。除了简单的算术外，它几乎不包含“数学”或证明。并且，尽管这本书对算法复杂度给予了适当的关注，但它并不涉及复杂度或计算理论以及类似的科学课题。此外，所有算法和数据结构都提供一些实际用例的示例。最后且重要的是，在 Lisp 中并没有关于算法方面的书，而且在我看来，用 Lisp 来教授算法是一个很好的主意。下一章将提供一个速成课程来掌握基本概念，然后我们将讨论各种 Lisp 编程方法以及它们将用于实现的算法。
这是一本入门书，并不是一本关于算法的“圣经”。它将绘制一幅全景图，并涵盖所有有必要的课题，进一步提高读者的算法知识。但是，它将不会深入探讨高级课题，例如持久性或概率数据结构、高级树、图和优化算法，以及特定领域的算法，例如机器学习、密码学或计算几何。所有这些课题都需要（通常也有自己的）单独的书籍。
关于 Lisp 的几句话
很长一段时间以来，我一直在考虑写一本关于 Lisp 的入门书，但有些思路还不完整，我无法在脑海中构建连贯的架构。后来，我有机会用 Lisp 来教授算法。在我看来，Lisp 非常适合演示数据结构和算法（但要注意，前提是学生应该愿意学习 Lisp），而讨论这些算法的实际方面是可以自然地解释语言。同时，这个课题几乎无须深入编程的邻近领域，如架构和程序设计、与其他系统的集成、用户界面以及使用高级语言特性（如类型或宏）。这样很好，因为这些课题对于入门书来说是多余的，而且在其他地方也有非常好的论述，且非常详细（参见 Practical Common Lisp 和 ANSI Common Lisp ）。
为什么 Lisp 对算法程序如此重要？原因之一是创建 Lisp 时就已经考虑到了这种用例。Lisp 支持所有适当的基本数据结构，如数组、哈希表、链表、字符串和元组。它还有一个数字塔，这意味着 Lisp 不会有溢出错误，因此，它在数学上要理智得多。再一个就是，Lisp 是为交互式开发风格创建的，因此实验周期非常短，没有编译→等待→运行→修改的繁文缛节，也没有不必要的约束，例如需要额外的注释（也称为类型），禁止变量突变或其他类似的东西。你只需在 REPL 中编写一个函数，运行它并查看结果即可。以我的经验来看，Lisp 程序看上去几乎就像个伪代码。与其他语言相比，它们有时可能略显冗长，但更清晰、更简单，并且与算法的逻辑表示直接兼容。
但是，为什么不去选择一种流行的编程语言呢？简而言之，它并不是最佳选择。本书可以考虑四种潜在的主流语言：C++、Java、Python 和 JavaScript。（当然，关于使用这些语言的算法资料已经够多了）前两个是静态类型的，这本身就是将它们用作教学语言的一大障碍。Java 也太冗长，而 C++ 又过于低级。但这些特性并不能阻止它们被广泛应用于大多数生产算法的代码中，而且你可能迟早会处理这些代码（如果还没有处理过的话）。此外，它们的标准库还为实用算法实现提供了很好的例子。但我相信，获得良好的概念理解将会让你在必要时能够轻松地适应其中一种语言，如果在学习这些语言的同时，又深入研究算法，会让事情变得复杂化，而这是没有必要的。Python 和 JavaScript 在很多方面是相反的选择：它们是动态的，并且提供了一定程度的交互体验（尽管比 Lisp 要差一些），但这些语言在许多方面都是“反算法”的。为了做到简单易懂，它们对程序员隐藏了太多东西，并且没有给予具体数据足够的控制权。在我看来，使用它们的标准库来教授算法就跟作弊一样，因为它们的基本数据结构往往不是它们声称的那样。Lisp 介于两者之间：它既具有高度交互性，又提供了足够的环境控制，同时又不会过于冗长和苛刻。以我拙见，为学习这种不熟悉的语法所付出的代价实在是微不足道。
然而，还有一种编程语言正在迅速流行起来，并被许多人认为是算法开发的不错选择——Rust。Rust 也是一种静态语言，虽然不像 Java 或 C++ 那么正式。但我既不是 Rust 方面的专家，也没打算成为 Rust 专家。此外，我认为关于静态语言的一般考虑也适用于 Rust。
算法复杂度
复杂度是本书每一页都会提及的一点：任何算法或数据结构的讨论都不能回避这个话题。除了正确性之外，复杂度就是每个算法的第二重要的性质——此外，如果只讲正确性，而忽略了复杂度，这通常无所谓；但相反的情况却是可能的：为了获得更好的复杂度，就得在某种程度上对正确性进行妥协。总的来说，算法理论与计算机科学其他学科的不同之处在于，它不涉及提出一种解决某些问题的可行（正确）方法，而是关于找到一种有效的方法来解决。其中，效率被理解为执行的操作和占用的存储空间的最小（或允许）的数量。
原则上，算法的复杂度取决于将执行的操作数量与输入大小的关系。它对计算机系统的可扩展性至关重要：对于特定的一组输入，解决编程问题可能很容易，但如果输入增加了一倍、十倍或百万倍，那么这个解决方案将会如何表现呢？这不是一个理论问题，任何通用算法的分析都应该对此有一个明确的答案。
复杂度是一个重要的研究课题：计算机科学的一个独立分支——复杂度理论之所以存在，就是为了研究它。然而，在整本书中，我们将尝试利用此类研究的最终结果，而不是深入钻研严格的证明或复杂的数学，特别是因为在大多数情况下，度量复杂度只是一个简单的计算问题。让我们看看下面的说明性示例代码：
此函数查找二维数组（矩阵）的最大元素：
它的复杂度是什么？要回答这个问题，我们只需计算执行的操作数：在内循环的每次迭代中，都有两次比较，涉及一次数组访问，有时，如果行星对齐，我们就会执行另一个访问进行赋值。内循环执行(array-dimension mat 1) 次，（我们称之为 m，其中m=3），外循环执行 (array-dimension mat 0) 次（本例中 n=2）。如果我们把这些都加起来，会得到：n * m * 4 作为上限，对于最坏的情况，每个序列数组元素都比前一个数组元素要大。根据经验，每个循环都将乘法运算添加到公式中，每个顺序块都添加一个加号。
在这个计算中，有两个变量（数组维数 n 和 m）和一个常量（每个数组元素执行的操作数）。有一种特殊的符号：Big-O，用来简化这种复杂度算法的最终结果的表示。将其中所有的常量都减少到 1，因此 m * 1 就变成了 m ，而且由于我们并不关心单个数组维度差异，所以可以用 n * n 来代替 n * m 。通过这样的简化，我们可以写出这个函数的最终复杂度结果： O(n²)。换言之，我们的算法在数据维度中具有二次复杂度（恰好是一个更广泛的称为“多项式复杂度”类的变体）。这意味着，通过将矩阵的维数增加 10 倍，算法的运算操作数将会增加 100 倍。然而，在这种情况下，更为自然的做法可能是关注运算操作数与矩阵元素数量的依赖关系，而不是矩阵的维数。我们可以观察到 n² 是元素的实际数量，所以它也可以写成 n，如果我们用 n 表示元素的数量，那么复杂度在元素的数量（O(n)）上是线性的。如你所见，理解我们正在谈论的 n 是多么重要！
在我们开始使用 Big-O 复杂度的事情来分析我们算法之前，关于 Big-O 复杂度还有一些事情需要了解。
1. 有 6 种主要的复杂度类算法：
时间常数（constant-time） （
O(1)）次线性（sublinear） （通常是对数 —
O(log n)）线性（linear） （
O(n)） 和次线性 （O(n * log n)）高阶多项式（higher-order polynomial） （
O(n^c)，其中c是大于 1 的常数）指数（exponential）（
O(с^n)，其中с通常是 2，但至少大于 1）纯粹只是疯狂情结（
O(n!)等等） — 我开玩笑地将它们称为O(mg)
每个类都是性能的阶跃函数的变化，特别是在规模上。由于我们将会讨论算法的例子，因此所有的算法都将被讨论。
最坏情况与平均情况的行为。在这个例子中，我们看到可能有两个操作计数：对于平均情况，我们可以假设大约一半的迭代需要赋值（这导致每个内循环中有 3 到 5 次操作）；而对于最坏的情况，这个数字将恰好为 4。由于 Big-O 将所有的数字都减少到 1，对于这个例子来说，这个差异是无关紧要的，但可能还有其他的数字，对这些数字来说，差异就要大得多，因此不能被丢弃。通常，对于这样的算法，都应该提到这两种复杂度（以及避免最坏情况的方法）：将在后面章节中阐述的快速排序算法就是一个很好的例子。
我们也看到了所谓的“Big-O 符号隐藏的常数因子”，也就是说，从算法复杂度的角度来看，是否需要在内循环中执行 3 个操作还是 30 个操作，这并不重要。然而，它在实践中却非常重要，我们将在检查二进制搜索时进行讨论。此外，由于这些隐藏因素（如，直到数据集达到一定大小），一些理论上复杂度更好的算法在许多实际应用中表现可能会变得更差。
最后，除了执行时间的复杂度外，还有空间的复杂度，它不是操作的数量，而是与输入大小成比例的存储空间使用量。一般来说，类似的方法也适用于其估算。
作者介绍：
Vsevolod Dyomkin，Lisp 程序员，居住在乌克兰基辅。精通乌克兰语、俄语和英语。目前正在撰写关于 Lisp 的书籍 Programming Algorithms in Lisp，该书将使用 CC BY-NC-ND 许可（创作公用许可协议），供公众免费阅读。
原文链接：
LISP, THE UNIVERSE AND EVERYTHING