二、算法基础：算法的定义、特性、设计要求和效率度量
好，咱们接着聊。上一章我们把数据结构理清了，这一章轮到算法了。说实话，很多初学者容易把这两者搞混，或者觉得算法就是“写个排序、写个查找”。其实远不止这些。我当年刚入行时，也以为算法就是背几个模板，直到有一次在项目中写了个O(n²)的循环去处理百万级数据，结果程序跑了整整两分钟没反应……嗯，从那以后，我才真正开始重视算法分析。
这一章，我们就从最根本的东西说起：算法到底是什么？它有什么特性？我们设计算法时该追求什么？以及——怎么衡量一个算法的好坏？
2.1 算法的定义
算法，说白了就是解决特定问题的一系列有限步骤。你想想看，做菜有菜谱，组装家具有说明书，算法就是计算机世界的“菜谱”。
更正式一点说：算法是对特定问题的求解步骤的一种描述，它是指令的有限序列，每条指令表示一个或多个操作。
我个人习惯把算法理解成“输入→处理→输出”的映射关系。比如你要排序一组数，输入是乱序数组，输出是有序数组，中间那套比较和交换的逻辑，就是算法。
核心要点：算法 ≠ 程序。程序是算法在某种语言下的具体实现，而算法是独立于语言的逻辑抽象。同一个算法，你可以用C写、用Python写、甚至用伪代码描述。
2.2 算法的特性
一个合格的算法，必须满足以下五个特性。我在面试新人时，经常拿这五点来考察对方的基础是否扎实。
- 有穷性：算法必须在执行有限步之后终止。无限循环不是算法，是bug。我曾经在项目中见过一个死循环的排序算法，服务器CPU直接飙到100%，吓得运维半夜打电话把我叫醒……
- 确定性：算法的每一步都必须有明确的定义，不能有二义性。比如“把数变大一点”这种描述就不合格，到底变大多少？
- 可行性：算法的每一步都必须是可执行的。你不能写“在O(1)时间内求出质数分布规律”，这做不到。
- 输入：算法可以有零个或多个输入。比如“输出当前时间”这个算法，就不需要输入。
- 输出：算法必须至少有一个输出。没有输出的算法没有意义，你算了一堆结果不告诉别人，那图啥？
避坑指南：我曾经在写递归算法时，忘记设置递归终止条件，结果函数无限调用自己，栈溢出直接导致程序崩溃。这就是违反了“有穷性”。记住：递归一定要有出口！
2.3 算法设计的要求
好，现在你知道算法是什么了。那设计一个算法时，我们该追求什么？我总结了四个字：正、可、健、效。
| 要求 | 说明 | 我的经验 |
|---|---|---|
| 正确性 | 算法必须能正确解决问题，对所有合法输入都能给出正确输出 | 我习惯先写几个边界测试用例，比如空输入、单元素输入、最大输入，跑通了再上线 |
| 可读性 | 算法要让人能看懂，便于交流和维护 | 别为了炫技写一堆位运算，三个月后你自己都看不懂 |
| 健壮性 | 算法能处理非法输入，不会崩溃 | 比如输入负数、空指针，算法应该给出合理反馈，而不是段错误 |
| 高效率 | 算法要尽量节省时间和空间资源 | 这是本章的重点，下面详细讲 |
你想想看，一个算法如果正确但慢得像蜗牛，或者快得像闪电但动不动就崩溃，那都不合格。好的算法，是这四个维度的平衡。
2.4 算法效率的度量方法
终于到了重头戏。怎么衡量一个算法的效率？两个维度：时间复杂度和空间复杂度。
2.4.1 事后统计法
最直接的方法：把算法写成程序，跑一遍，用计时器算时间。但这个方法问题很大——
- 依赖硬件：同样的算法，在i3和i9上跑，时间能差好几倍
- 依赖语言：C语言和Python跑同一个算法，速度天差地别
- 依赖数据：输入规模不同，时间差异巨大
所以，我们真正需要的是事前分析估算，也就是用数学方法分析算法的效率。
2.4.2 事前分析估算——大O表示法
大O表示法，说白了就是描述算法执行时间随输入规模增长的趋势。它不关心具体秒数，只关心“当n很大时，算法大概有多慢”。
常见的复杂度从快到慢排序：
| 大O记号 | 名称 | 示例 |
|---|---|---|
| O(1) | 常数阶 | 数组随机访问 |
| O(log n) | 对数阶 | 二分查找 |
| O(n) | 线性阶 | 遍历数组 |
| O(n log n) | 线性对数阶 | 归并排序、快速排序平均情况 |
| O(n²) | 平方阶 | 冒泡排序、双重循环 |
| O(2ⁿ) | 指数阶 | 递归斐波那契（未优化） |
| O(n!) | 阶乘阶 | 旅行商问题暴力解法 |
注意：当n=100时，O(n²)的算法需要执行10000步，而O(n log n)只需要约700步。当n=10000时，差距更是天壤之别。所以，选择正确的算法比优化代码细节重要得多。
2.4.3 如何分析一段代码的时间复杂度？
我教你一个简单的方法：找循环。看代码里最深层的循环执行了多少次。
// 示例1：O(n)
for (int i = 0; i < n; i++) {
printf("%d\n", i);
}
// 示例2：O(n²)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d %d\n", i, j);
}
}
// 示例3：O(log n)
for (int i = 1; i < n; i = i * 2) {
printf("%d\n", i);
}
为什么会这样？示例1循环n次，示例2循环n×n次，示例3每次i翻倍，所以循环次数是log₂n。你想想看，当n=1024时，示例3只循环10次，而示例2要循环超过100万次——这就是算法效率的差距。
2.4.4 空间复杂度
时间复杂度看时间，空间复杂度看内存。同样用大O表示。
比如你写了个递归函数，每递归一次就压一次栈，深度为n，那空间复杂度就是O(n)。如果你只用了几个临时变量，不管n多大都只占固定内存，那就是O(1)。
我的建议：在嵌入式开发或内存受限的环境中，空间复杂度比时间复杂度更敏感。我曾经在STM32上写算法，RAM只有64KB，一个O(n)的辅助数组就把内存吃光了。这时候就得用原地算法（in-place），用时间换空间。
2.5 知识体系总览
下面这张图，把本章的核心内容串起来了。你可以把它当作一个思维导图来看。
这张图把算法基础拆成了四个模块：定义、特性、设计要求、效率度量。其中效率度量又分为时间和空间两个维度。你学完这一章，应该能对着这张图把每个点都讲清楚。
好了，这一章的内容就到这里。算法这东西，光看是学不会的，一定要动手写、动手分析。我建议你找几个简单的算法（比如冒泡排序、二分查找），自己画一下流程图，算一下复杂度，感受一下“大O”到底是怎么来的。
下一章，我们会把这些理论用到实际的数据结构中去，看看链表、栈、队列这些结构对应的算法复杂度是什么样的。