算法入门：计算机如何思考

算法入门：计算机如何思考

从厨房到指尖：算法的无处不在

清晨，你走进厨房准备早餐。冰箱里躺着几枚鸡蛋，一盒牛奶，还有昨天剩下面包。你打开手机，搜索“鸡蛋饼的做法”，屏幕上立刻出现一段文字：“第一步，打两个鸡蛋到碗里；第二步，加入适量面粉和水，搅拌均匀；第三步，平底锅预热，倒入蛋液；第四步，煎至两面金黄即可。”你按照这些步骤操作，几分钟后，一份热腾腾的早餐摆在了餐桌上。

这个过程再普通不过，几乎每个人每天都在经历。但如果我们稍微转换一下视角，就会发现一个有趣的现象：你手中的那份食谱，本质上就是一份算法。它告诉你要做什么（输入），包含一系列明确的步骤（处理过程），最终产生一个可食用的结果（输出）。更妙的是，这份食谱可以重复使用——今天早上做鸡蛋饼，明天晚上做葱油饼，都可以用同样的模板，只是换换材料而已。

让我们再来看另一个例子。当你打开导航软件，输入目的地时，系统会在几秒钟内为你规划出一条路线。这条路线可能不是最短的，但一定是“最优”的——它综合考虑了距离、路况、预计时间，甚至你的偏好（是否走高速、是否避开收费路段）。你可能会好奇：计算机是如何在浩如烟海的可能路线中，快速找到这条最优路径的？答案同样是算法。计算机运用一套精妙的搜索策略，在瞬间遍历了数以万计的路线组合，最终将结果呈现在你的手机屏幕上。

这两个例子揭示了一个深刻的道理：算法并非计算机科学家的专属产物，而是深深嵌入我们日常生活的一种思维方式。从烹饪到出行，从整理房间到完成作业，我们无时无刻不在与算法打交道。理解算法，就是理解这个世界运行的基本逻辑之一。

抽象与形式化：什么是算法

从具体到抽象的认识过程

让我们继续深入思考上面两个例子。在食谱的例子中，我们注意到几个关键要素：首先，食谱包含一系列明确的操作步骤——“打鸡蛋”“加面粉”“搅拌”“加热”，每一步都有清晰的指示，不会产生歧义；其次，这些步骤是有限的——你不可能无限地添加步骤而不完成烹饪；再次，这些步骤都是可执行的——只要你有基本的厨艺和工具，就能够完成每一个步骤；最后，当你完成所有步骤后，你会得到一个具体的结果——一份可以食用的鸡蛋饼。

如果我们把这些具体要素抽取出来，去掉“鸡蛋”“面粉”这些特定的具体对象，就能得到一个更加抽象的概念：这个概念包含一组有穷的、确定的、可执行的操作步骤，并且能够产生一个明确的结果。这就是算法（Algorithm）的雏形。

算法的概念有着悠久的历史。“算法”一词源自阿拉伯数学家阿尔·花剌子模（Al-Khwarizmi，约公元780-850年）的名字。他在著作《印度计算术》中系统地介绍了十进制计数法和代数方法，被认为是代数学的奠基人之一。然而，算法的思想远比这个名称古老。古巴比伦人留下了求最大公约数的方法，古希腊人发明了筛法求素数，中国古代数学家发展出了求高次方程根的技艺——这些都是算法的早期形态。

算法的正式定义

在现代计算机科学中，算法被定义为：一个由有限步骤组成的、能够解决某个特定问题或完成某项具体任务的明确指令序列。这个定义看似简单，却蕴含着丰富的内容。让我们逐一拆解其中的关键词。

有限步骤意味着算法必须在有限的时间内终止。想象一个永远执行下去的程序——它可能看起来很“智能”，但从算法的角度来看，它是无效的。一个真正的算法必须能够结束，产生最终结果。这个特性被称为有穷性，是算法区别于一般计算过程的重要标志。

明确指令意味着每一步操作都必须清晰、无歧义。当我们说“加入适量面粉”时，这个指令在人类的厨房里可能没有问题——一个有经验的厨师知道“适量”是多少。但在算法的语境下，这种模糊表述是不被允许的。算法中的每一条指令都必须能够被精确地执行，没有任何歧义。这个特性被称为确定性，是算法的核心要求之一。

可执行意味着算法中的每一步都必须是当前执行者力所能及的操作。对于计算机算法来说，这意味着每一步都必须在有限时间内完成，并且能够被机器自动执行。这个特性被称为可行性。如果一个算法包含“将π的小数点后每一位都写出来”这样的步骤，那么它就不是一个可行的算法，因为这个过程永远不会结束。

解决问题或完成任务意味着算法必须有明确的目标。这个目标就是算法的输出。当我们执行完算法的所有步骤后，应该得到一个明确的、有意义的结果。输出是算法的驱动力——它告诉我们为什么要执行这些步骤，以及怎样才算“成功”。

除了输出之外，算法通常还需要输入。输入是算法处理的对象，是产生输出所必需的原材料。在食谱的例子中，输入就是各种食材；在导航的例子中，输入就是你当前位置和目的地位置。有些算法可以没有输入——比如一个总是输出当前时间的算法，它的“输入”是隐含在系统时钟里的。

算法的五大特性：算法的DNA

通过以上的分析，我们可以系统地总结出算法的五大核心特性。这些特性就像算法的DNA，决定了什么是算法、什么不是算法。

有穷性：算法必须停止

有穷性（Finiteness）是算法的首要特性。一个算法必须在执行有限个步骤之后终止，不能无限期地运行下去。这看起来是一个理所当然的要求，但其中蕴含着深刻的思考。

考虑这样一个问题：给定一个正整数$n$，求所有能够整除$n$的正整数（即$n$的所有因数）。解决这个问题的方法是明确的：遍历从1到$n$的所有整数，检查每一个数是否能整除$n$。由于这个遍历过程是有限的（最多$n$个数字），算法必然会在有限时间内结束。这就是有穷性的体现。

然而，有穷性也带来了一个有趣的问题：是否所有问题都能用有穷的算法来解决？答案是否定的。有些问题本身就是“不可判定的”——不存在任何有穷的算法能够解决它们。最著名的例子是停机问题（Halting Problem）：给定任意一个程序和它的输入，是否存在一个通用算法，能够判断这个程序在这个输入上是否会停止？答案是：不存在。这样的算法会导致逻辑悖论。

但对于我们日常接触的大多数问题——无论是排序一组数字、查找一篇文章中的某个词，还是规划一条最短路径——都是有穷的，都是可以用算法解决的。

可行性：每一步都必须能执行

可行性（Effectiveness）意味着算法中的每一个操作都必须是切实可行的，必须能够在有限时间内由机器自动完成。这个特性看似简单，却常常被忽视。

考虑这样一个问题：求两个正整数的最大公约数。欧几里得算法给出了优雅的解决方案：用较小数去除较大数，取余数；然后用余数去除之前的较小数，再次取余；重复这个过程，直到余数为零，此时的除数就是最大公约数。这个算法的每一步——除法、取余、比较——都是现代计算机能够轻松完成的基本操作，因此是可行的。

但是，如果我们的算法中包含“将当前的余数分解质因数”这样的步骤，而分解质因数对于某些大整数来说是一个极其困难的任务，那么这个算法虽然理论上可行，但在实践中却可能无法在合理时间内完成。这引出了一个重要的区分：理论上的可行性和实践中的可行性。算法理论主要关注前者，而计算机科学更关心后者——这就是时间复杂度和空间复杂度研究的意义所在。

确定性：没有歧义的指令

确定性（Definiteness）要求算法中的每一条指令都必须清晰、无歧义。当一个算法被不同的人、在不同的时间执行时，只要输入相同，就应该产生相同的输出。

让我们对比两个例子：

算法A：求一个数的平方根 1. 估算一个近似值 2. 不断调整这个近似值，直到它足够接近真实值

算法B：用牛顿迭代法求平方根 1. 设$x_0$为初始近似值（任意正数） 2. 对于$k = 0, 1, 2, \ldots$，计算$x_{k+1} = \frac{1}{2}(x_k + N/x_k)$，其中$N$是被开方数 3. 当$|x_{k+1} - x_k| < \epsilon$时停止，$x_{k+1}$即为近似平方根

算法A看起来直观，但“估算”和“调整”都是模糊的概念，不同的执行者可能会采取完全不同的策略。算法B则完全不同——每一步都有精确的数学公式，任何人按照这个步骤执行，都会得到相同的结果。算法B是确定性的，算法A不是。

在计算机编程中，确定性的要求转化为对变量赋值、条件分支、循环终止条件的精确控制。程序员必须明确告诉计算机每一步要做什么、什么时候停止，否则程序就会陷入混乱。

输入：算法的原材料

输入（Input）是算法处理的对象。一个算法的输入可以是零个、一个或多个。输入为算法提供了操作所需的原材料，是算法运行的起点。

以我们熟悉的各种应用为例：

• **计算器**的输入是两个或多个数字以及一个运算符
• **搜索引擎**的输入是一个或多个关键词
• **图像编辑软件**的输入是一张图片以及各种操作指令
• **天气预报程序**的输入是温度、湿度、气压、风速等气象数据

算法的输入必须满足一定的前提条件，这些条件被称为前置条件（Precondition）。例如，一个排序算法的输入必须是可比较的元素序列；一个求平均数的算法的输入必须是非空集合（不能对空集合求平均）。

理解输入的前置条件非常重要。它告诉我们算法在什么情况下可以使用，什么情况下不能使用。如果不满足前置条件，算法的行为可能是未定义的——它可能产生错误的结果，或者直接崩溃。

输出：算法的目标

输出（Output）是算法的目的所在，是算法处理输入后产生的结果。没有输出的算法是毫无意义的——它消耗了时间和空间，却不产生任何价值。

输出可以分为几类：

• **单个结果**：如求和算法输出一个总和
• **多个结果**：如分解质因数算法输出一系列质因数
• **布尔值**：如判断质数算法输出“是”或“否”
• **状态指示**：如检查括号匹配算法输出“匹配成功”或“匹配失败”
• **复合结构**：如最短路径算法输出一条完整的路径

与输入的前置条件相对应，算法通常还承诺后置条件（Postcondition）——即算法成功结束后，输出必然满足的性质。例如，排序算法的后置条件是：输出序列中的元素按升序排列，且包含所有原始元素（不多不少）。

煎蛋与泡面：生活中的算法分析

现在我们已经建立了算法的基本概念，接下来让我们引入算法分析的核心工具——时间复杂度和空间复杂度。这两个概念帮助我们回答一个关键问题：当我们说一个算法“更好”时，究竟意味着什么？

时间复杂度：算法快不快

时间复杂度（Time Complexity）衡量的是算法执行所需的时间。但这里有一个微妙之处：我们不关心算法在特定计算机上运行的确切秒数（那会受到CPU性能、编程语言、编译器优化等因素的影响），而关心算法执行步骤的数量随输入规模增长的趋势。

让我们用泡面的例子来理解这个概念。

当你决定泡一碗方便面时，最简单的方法是：烧水、撕开包装、放入面饼、倒入热水、等待三分钟、加入调料、搅拌、享用。这个过程有多少个步骤？如果我们只关心“泡一碗面”这件事，那么步骤数是固定的——大约七八步。无论你是泡一碗还是泡十碗，步骤数都基本不变。

但是，考虑另一种情况：你需要泡$n$碗面。如果采用同样的方法，你需要重复“烧水、倒入、等待”这个过程$n$次，总步骤数与$n$成正比。如果用数学语言来描述，我们说这个算法的时间复杂度是$O(n)$，意思是当输入规模为$n$时，算法的时间随$n$线性增长。

现在，考虑一个更复杂的场景：你有$n$碗面，但只有一口锅，每次只能煮一碗。在这种情况下，无论你如何优化，都必须依次煮完所有面条，总时间仍然是$O(n)$。

但是，如果这口锅足够大，一次能放$m$碗面呢？这时，情况变得有趣了：你需要$\lceil n/m \rceil$轮才能煮完所有面条。如果$m$是固定的，那么总时间仍然是$O(n)$——只不过常数因子变小了。

这些例子说明了一个重要的原则：在分析时间复杂度时，我们关注的是增长趋势，而不是具体数值。$O(n)$意味着时间与输入规模成正比；$O(n^2)$意味着时间与输入规模的平方成正比；$O(1)$意味着时间是常数，与输入规模无关。

空间复杂度：算法占多少内存

空间复杂度（Space Complexity）衡量的是算法执行过程中占用的内存空间。与时间复杂度类似，我们关注的是空间占用随输入规模增长的趋势。

继续泡面的例子。如果你在泡面前需要把每碗面的配料（酱包、菜包、调味包）提前摆好，然后一次性煮，那么你就需要额外的桌面空间来放置这些配料。如果你有$n$碗面，你就需要$O(n)$的空间来放置配料。

但是，想一个更聪明的办法：你可以在需要时才取出每碗面的配料，而不是一次性全部摆出来。这样，你只需要$O(1)$的额外空间——无论有多少碗面，都只需要很小的空间来临时放置当前需要的配料。

这个例子展示了空间复杂度的实际意义。在计算机科学中，空间往往和時間一样宝贵。一个时间很快但空间需求巨大的算法，可能在内存有限的设备上无法运行；一个空间需求很小但时间很慢的算法，可能会让用户等待太久。因此，算法设计常常需要在时间和空间之间寻找平衡。

大O表示法：增长趋势的语言

在算法分析中，大O表示法（Big O Notation）是最常用的描述时间或空间复杂度的工具。它帮助我们忽略常数因子和低阶项，只关注增长最快的项。

让我们通过几个例子来理解大O表示法：

• **$O(1)$ 常数时间**：算法的执行时间与输入规模无关。无论输入多大，所需时间都是固定的。例子：在数组中通过索引直接访问元素。
• **$O(\log n)$ 对数时间**：每次操作将问题规模缩小一半。例子：二分查找，在有序数组中查找目标值。
• **$O(n)$ 线性时间**：执行时间与输入规模成正比。例子：遍历数组找出最大值。
• **$O(n \log n)$ 线性对数时间**：介于线性和平方之间，许多高效的排序算法（如归并排序、快速排序）的复杂度。
• **$O(n^2)$ 平方时间**：执行时间与输入规模的平方成正比。例子：检查数组中所有可能的两两组合。
• **$O(2^n)$ 指数时间**：每增加一个输入，所需时间翻倍。例子：生成所有可能的子集。

下面这张表总结了常见的时间复杂度及其增长速度：

| 复杂度 | $n=10$ | $n=100$ | $n=1000$ | 增长率 | |--------|--------|---------|----------|--------| | $O(1)$ | 1 | 1 | 1 | 常数 | | $O(\log n)$ | 3.3 | 6.6 | 10 | 极慢 | | $O(n)$ | 10 | 100 | 1000 | 线性 | | $O(n \log n)$ | 33 | 664 | 10000 | 较快 | | $O(n^2)$ | 100 | 10000 | 1000000 | 平方 | | $O(2^n)$ | 1024 | $1.27 \times 10^{30}$ | 巨大 | 指数 |

从表中我们可以清晰地看到不同复杂度之间的巨大差异。当$n$增大时，高阶复杂度的算法会变得完全不可用——这就是算法分析的价值所在，它让我们在设计系统之前就能预见性能瓶颈。

从煎蛋到复杂系统：算法复杂度的实例分析

煎一个完美的蛋：简单算法的威力

让我们用一个生活中常见的问题来展示算法分析的实际应用：如何判断一个数是否为质数。

质数（Prime Number）是只能被1和它本身整除的正整数。从2开始，质数序列是：2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

现在，我们要判断一个数$n$是否为质数。最直观的方法是：检查所有从2到$n-1$的整数，看是否有能整除$n$的。如果找到了任何一个这样的数，那么$n$不是质数；如果没有找到，那么$n$是质数。

这个算法的时间复杂度是$O(n)$——我们需要检查最多$n-2$个数。

但我们可以做得更好。如果$n$不是质数，它必然有一个因数不大于$\sqrt{n}$。这是因为：如果$n = a \times b$，且$a \leq b$，那么$a \leq \sqrt{n}$。因此，我们只需要检查从2到$\sqrt{n}$的整数。

这个优化后的算法时间复杂度是$O(\sqrt{n})$。当$n$是1000000时，第一种算法需要检查999998个数，第二种算法只需要检查1000个数——快了整整1000倍！

```python

判断质数的两种算法

def is_prime_naive(n): """朴素算法：O(n)时间复杂度""" if n <= 1: return False for i in range(2, n): if n % i == 0: return False return True

def is_prime_optimized(n): """优化算法：O(√n)时间复杂度""" if n <= 1: return False if n <= 3: return True if n % 2 == 0 or n % 3 == 0: return False i = 5 while i * i <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True ```

这个例子告诉我们：算法优化往往能带来质的飞跃。同样的问题，从$O(n)$优化到$O(\sqrt{n})$，当输入规模增大时，节省的时间是惊人的。

整理书架：排序的智慧

让我们再来看一个更加生活化的问题：如何整理书架上的书？假设你有$n$本书，它们杂乱无章地放在书架上，你希望按照书名的字母顺序排列它们。你会怎么做？

一种方法是：选择排序（Selection Sort）。它的思路很简单：找出最前面$n$本书中最应该放在第一位的那本（书名字母顺序最靠前的），把它换到第一位；然后在剩下的$n-1$本书中重复这个过程。

这个算法需要多少次比较？如果每轮都要扫描剩余的书来找最小值，那么第一轮需要$n-1$次比较，第二轮需要$n-2$次比较，……，最后一轮需要1次比较。总比较次数是$(n-1) + (n-2) + \cdots + 1 = n(n-1)/2$，即$O(n^2)$。

但还有更聪明的方法：插入排序（Insertion Sort）。它的思路更符合我们整理书架的直觉——把一本书拿起来，找到它在已排序部分中的正确位置，插入进去。

插入排序在最好的情况下（书已经基本有序）只需要$O(n)$次比较；在最