1. 从“做事步骤”到“计算过程”
这一节先回答一个最基本的问题：什么叫算法。
算法是一种定义良好的计算过程。它接收一个或一组输入，经过有限个明确步骤，在有限时间内产生一个或一组输出。也可以说，算法就是把输入转换成输出的一套清楚规则。
这里有三个关键词：
- 输入：问题给定的数据
- 过程：一系列明确、可执行的步骤
- 输出：满足要求的结果
所以，算法不是“模糊的思路”，而是能够真正执行的求解过程。
2. 算法是在解决“计算问题”
算法总是对应某个计算问题。
一个计算问题，先要说明：
- 输入是什么
- 输出应该满足什么条件
算法则负责给出一套具体方法，使得每个合法输入都能算出对应的结果。
例 1：排序问题
输入：
⟨a1,a2,…,an⟩ \langle a_1, a_2, \dots, a_n \rangle⟨a1,a2,…,an⟩
输出：
输入序列的一个重排，并且满足从小到大有序。
例如输入：
⟨31,41,59,26,41,58⟩ \langle 31, 41, 59, 26, 41, 58 \rangle⟨31,41,59,26,41,58⟩
输出应为：
⟨26,31,41,41,58,59⟩ \langle 26, 31, 41, 41, 58, 59 \rangle⟨26,31,41,41,58,59⟩
这个例子说明了一点：
算法不是为了“写程序”而存在，而是为了把一个问题的输入输出关系真正实现出来。
3. 正确算法是什么意思
一个正确算法，必须满足两个条件：
(1) 能停下来
算法不能无限循环，必须在有限时间内结束。
(2) 结果是对的
结束还不够，输出还必须真的是这个问题的正确答案。
所以，判断一个算法，至少要问两个问题：
- 它会不会停机？
- 它算出来的是不是对的？
因此，正确算法可以理解为：
对每个合法输入，都能在有限时间内停止，并输出正确结果的算法。
4. 一个问题通常不只有一种算法
排序是最好的说明。
同样是排序，可以有很多不同做法。真正选择哪一种，要看很多条件：
- 数据量大不大
- 数据是不是已经部分有序
- 元素取值有没有特殊限制
- 机器结构是什么
- 数据放在内存里还是磁盘里
这说明：
算法不是“有没有办法做”，而是“用什么方式做更合适”。
也正因为这样，后面才会学习复杂度分析。因为不同算法虽然都能解决问题，但效率可能差得非常大。
5. 算法不只出现在教材例子里
算法的应用范围非常广。比如：
- 生物信息：DNA 序列分析
- 互联网：路由选择、搜索
- 电子商务：公钥密码、数字签名
- 资源分配：把有限资源用在最合适的位置
还可以看到一些具体问题：
最短路径
给定地图或网络，怎样从一个点走到另一个点，并且总路程最短。
拓扑排序
如果一个零件依赖另一个零件，应该按照什么顺序安排，才能保证前置部分先完成。
聚类
根据相似性把对象分组，例如辅助判断肿瘤更可能属于哪一类。
压缩
怎样用更短的编码表示信息，减少存储空间。
这些例子想说明一件事：
算法不是脱离现实的“数学游戏”，而是很多系统真正工作的底层逻辑。
6. 数据结构为什么会在这里出现
这一节还专门提到数据结构。
数据结构是组织和存储数据的方法。
学习算法时，不能把它和数据结构分开，因为很多算法之所以快，不只是步骤设计得好，还因为数据放得对。
例如：
- 查找时，数组、链表、树的效率不同
- 插入、删除时，不同结构成本也不同
所以可以先有一个直觉：
算法解决“怎么做”，数据结构解决“数据怎么放”。
两者通常是一起决定效率的。
7. 不是所有问题都有高效算法
有些问题，我们知道高效算法，比如最短路径。
但也有些问题，目前没有已知的高效精确算法。典型例子就是旅行商问题。
这类问题提醒我们：
- 有时候可以求精确解
- 有时候只能求近似解
- 有时候重点不是“最优”，而是“足够好且算得快”
所以算法学习从一开始就不是“万能解法大全”，而是在理解：
- 哪些问题容易
- 哪些问题难
- 难问题该怎么处理
8. 配图
9. 小结
- 算法是定义良好的计算过程：输入经过明确步骤，在有限时间内变成输出。
- 算法总是对应某个计算问题，问题先规定输入输出关系，算法再给出具体做法。
- 一个正确算法必须同时满足：能停机，且结果正确。
- 同一个问题通常有多种算法，区别不只在能不能做出来，更在效率和适用条件。
- 算法广泛存在于排序、搜索、路由、加密、优化等现实场景中。
- 数据结构和算法密切相关，前者影响数据组织方式，后者影响求解步骤。
- 并不是所有问题都有高效精确算法，算法学习也包含对“难问题”的认识。
