算法与问题求解入门：为什么它是计算机科学的灵魂

本节你将能

学完这一节，你将能说清三件事：什么是算法、为什么同样的任务不同算法快慢天差地别、以及怎么判断一个算法"对"且"快"。这是后面排序、查找、动态规划、图论所有内容的总入口。

一、算法是什么：不只是"写代码"

严格地说，algorithm 是解决某类问题的一组有限、确定、可执行的步骤。它独立于任何编程语言——你可以用中文描述一个算法，也可以用 Python 或纸笔实现它。日常例子俯拾皆是：菜谱是算法，导航 App 规划路线是算法，甚至"把一堆无序的试卷按学号排好"也是算法。

与程序的区别在于：程序是算法在某个机器、某种语言上的具体实现，会受制于内存、I/O、编译器；而算法是思想本身。计算机科学的基石，正是把这些思想抽象出来、比较优劣、证明对错。

二、为什么必须研究算法：效率差出成千上万倍

同一个问题，不同算法可能慢如蜗牛和快如闪电。最经典的例子是排序：把 100 万个数字排好序，朴素方法要约 10^12 步，而好的算法只需约 2×10^7 步——差距是五万倍。数据越大，差距越夸张。这正是后面 B 系列（排序）要系统讲清的事。

权威教材 CLRS《算法导论》开篇就点明：算法的效率，决定了什么是"可行"，什么是"不可能"。今天的搜索引擎、短视频推荐、加密支付，背后都是算法在扛。

三、正确性从哪来：循环不变量

写对一段循环比你想象得难。CLRS 第 2.1 节给出了一套通用证明工具——loop invariant：在循环每次迭代前后都保持为真的某个性质。证明三步：初始化（循环前为真）、保持（若某轮前为真，则轮后也为真）、终止（循环结束时，不变量能推出目标已达成）。用它能严谨证明插入排序确实排好了序，而不是"跑一遍看起来对"。

四、效率的语言：大 O 直觉

我们不数"具体几步"，而是看输入规模 n 增长时，步数怎么随之增长。这就是Big-O 要做的事（下一节 A2 详讲）。先记住直觉：O(n) 随数据线性增长，O(log n) 增长极慢（二分查找的奥秘），O(n²) 则会随数据爆炸。同一个功能，选 O(n) 还是 O(n²)，在大数据下天壤之别。

五、算法与数据结构：一体两面

没有数据结构，再好的算法也无处安放。链表、哈希表、堆、树，每一种都为特定操作提供了"快"的土壤。后面 C 系列（数据结构）会讲清：为什么 哈希表 能 O(1) 查字典、为什么 堆 能随时取最小值。算法设计，往往先问"用什么数据结构"。

六、第一个例子：线性查找 vs 二分查找

在一本 1000 页的电话簿里找名字：从头翻（线性查找）最坏翻 1000 次；每次都翻到中间、丢掉一半（二分查找）只需约 10 次。后者快 100 倍，前提是"书已按名字排好序"。这个对比藏着算法设计的核心权衡：预处理（排序）换查询加速。二分查找将在 D3 单独成节。

小结与下一步

算法 = 精确的步骤 + 可证明的正确 + 可度量的效率。接下来建议按轨道推进：B1 排序（让数据有序，解锁二分）→ C3 链表（最基础的数据结构）→ A3 主定理（给递归算法算复杂度）。整个算法通关轨道已在缺口体系中排好优先级，逐个击破即可。

图1：算法（思想）与设计程序（实现）的关系示意 ｜ 图2：不同排序算法在 n=10^6 时的步数对比（对数坐标）