Classification of algorithms

欢迎来到算法分类的世界！

在本章中，我们将深入探讨计算理论（Theory of Computation）的核心。你已经学会了如何编写算法，但你有没有想过，计算机科学家是如何判断一个算法是否“更优”的呢？如果你有两种不同的方法来整理一份名单，当名单上有数百万个名字时，你如何知道哪一种方法会更快？

我们将学习如何使用大 O 符号（Big-O notation）来衡量算法的“效率”，并会发现有些问题是如此困难，以至于即使是世界上最强大的计算机，也无法在合理的时间内解决它们。如果一开始觉得这些概念有点抽象，不用担心——我们会循序渐进地为你拆解！

1. 比较算法

当我们比较算法时，并不是看它们在你的笔记本电脑上运行需要多少秒。为什么？因为更快的处理器总是会让算法看起来“更好”。相反，我们关注的是复杂度（Complexity）。

时间和空间效率

衡量算法主要有两种方式：
• 时间复杂度（Time Complexity）：随着输入规模增加，执行所需的时间是多少？
• 空间复杂度（Space Complexity）：随着输入增长，算法需要多少内存（RAM）？

关键问题：问题规模 \( (n) \)
最重要的因素是问题规模（problem size），我们通常称之为 \( n \)。例如，如果你要在名单中搜索一个名字，\( n \) 就是名单中名字的数量。当 \( n \) 变大时，我们想知道计算机需要增加多少工作量。

比喻：想象你在整理房间。如果 \( n \) 是地板上物品的数量，“线性”算法意味着整理 10 件物品需要 10 分钟，整理 20 件需要 20 分钟。但如果整理 20 件物品突然需要 400 分钟，那你所用的算法就非常没有效率了！

重点小结：我们比较算法是基于它们的性能如何随问题规模 \( (n) \) 而变化，而不是基于硬件的运行速度。

2. Big-O 背后的数学

为了理解算法是如何增长的，我们使用一些数学函数。你不需要成为数学天才，只需要认出这些函数的“形态”即可：

• 线性函数： \( y = 2x \)（一条直线。如果输入加倍，所需时间也加倍。）
• 多项式函数： \( y = 2x^2 \)（一条曲线。如果输入加倍，所需时间会变成四倍！）
• 指数函数： \( y = 2^x \)（增长速度极其惊人。即使输入很小，它也会“爆炸式”增长。）
• 对数函数： \( y = \log_{10} x \)（理想的状态！随着输入增长，所需时间增加得非常缓慢。）

你知道吗？集合的排列（Permutation）就是成员的一种排序方式。排列 \( n \) 个不同对象的方法数量是 \( n \) 阶乘（\( n! \)）。例如，如果你有 3 本书，那么排列它们的方法有 \( 3 \times 2 \times 1 = 6 \) 种。阶乘的增长速度比指数函数还要快！

3. 复杂度顺序（Big-O 符号）

Big-O 符号是一种用于描述算法时间需求最坏情况（worst-case scenario）的速记法。它告诉我们该算法的“复杂度顺序”。

常见的 Big-O 排名（从最快到最慢）

1. 恒定时间 \( O(1) \)：无论输入规模大小，所需时间始终相同。（例如：检查列表中的第一个数字是否为偶数）。
2. 对数时间 \( O(\log n) \)：非常有效率。常见于“分治法（divide and conquer）”算法，例如二分查找法（Binary Search）。
3. 线性时间 \( O(n) \)：时间随输入规模成正比增长。（例如：线性查找法（Linear Search））。
4. 多项式时间 \( O(n^2) \)：时间与输入的平方成正比。常见于嵌套循环（nested loops）。（例如：冒泡排序法（Bubble Sort））。
5. 指数时间 \( O(2^n) \)：极其缓慢。将输入规模加倍，所需时间会呈指数级增加。

如何推导复杂度：
观察代码时，我们只关注增长最快的部分。如果一个程序包含线性部分和平方部分，我们称其为 \( O(n^2) \)，因为当 \( n \) 变得非常大时，\( n^2 \) 部分才是真正起决定性作用的因素。

快速复习盒：
• \( O(1) \)：瞬间完成。
• \( O(n) \)：平稳增长。
• \( O(n^2) \)：快速增长。
• \( O(2^n) \)：危险的增长！

4. 计算的极限

尽管计算机每年的速度都在提升，但算法复杂度和硬件限制仍然规定了我们能计算的极限。有些算法太过于复杂，即使在超级计算机上运行，所花的时间也会比宇宙的年龄还要长！

可处理问题与不可处理问题（Tractable vs. Intractable）

• 可处理问题（Tractable）：指可以在多项式时间（polynomial time）（\( O(n^k) \)）或更短时间内解决的问题。我们认为这些问题在合理时间内是“可做到的”。
• 不可处理问题（Intractable）：指没有多项式时间解决方案的问题（它们可能是指数级的）。在技术上它们是“可解的”，但在 \( n \) 值很大时，实际上是不可能解决的。

启发式方法（Heuristic Approach）：
当我们面临不可处理的问题时，通常会使用启发式（Heuristic）。这是一种“经验法则”或“够好就行”的方法。它可能无法给出 100% 正确的完美答案，但能在合理时间内给出一个令人满意的答案。
例子：GPS 在拥有多达数百万种路径的城市中寻找“最佳”路线。它会使用启发式方法快速找出一个非常好的路线，而不是计算每一条可能的路径。

5. 停机问题（The Halting Problem）

是否有计算机完全无法解决的问题？有的！这些被称为不可计算问题（non-computable problems）。

最著名的例子就是停机问题（Halting Problem）。
定义：停机问题询问是否可以编写一个程序，去检查任何其他程序及其输入，并判断该程序最终会停止（halt）还是会陷入无限循环永远执行下去。

定论：1936 年，艾伦·图灵（Alan Turing）证明了停机问题是不可解的（unsolvable）。这样的程序永远不存在。
这为什么重要？它证明了计算能力存在根本性的限制。有些问题是逻辑和计算机永远无法回答的。

避免常见错误：不要混淆“不可处理（Intractable）”与“不可解（Unsolvable）”。
• 不可处理（Intractable） = 可解，但花费时间太长。
• 不可解（Unsolvable/Non-computable） = 计算机永远不可能解决。

6. 图灵机（Turing Machines）

图灵机是一个计算机的理论模型。它帮助我们理解计算的极限。
它包含：
• 一组有限的状态（finite set of states）（显示在状态转换图中）。
• 一个有限的符号字母表（finite alphabet）。
• 一条被划分为方格的无限纸带（infinite tape）。
• 一个可以在纸带上一次移动一格的读写头（read-write head）。

通用图灵机（Universal Turing Machine）是一种可以模拟任何其他图灵机的机器。它是现代计算机的理论基础——单一台机器就能运行任何程序！

关键总结：图灵机为“什么是可计算的”提供了正式定义。如果图灵机做不到，任何计算机也都做不到。

做得好！你已经完成了关于算法分类的笔记。记住：效率的关键在于增长速度，而 Big-O 就是你衡量它的工具！