算法概述
什么是算法？
算法 (Algorithm) 是解决特定问题的一系列定义明确的指令。就像菜谱教你如何做菜一样，算法教计算机如何处理数据、执行计算或完成自动化推理任务。
算法的五大特性：
- 有穷性 (Finiteness): 算法必须在有限步骤内结束。
- 确定性 (Definiteness): 每一步都有确切的含义，无二义性。
- 输入 (Input): 有 0 个或多个输入。
- 输出 (Output): 至少有一个输出。
- 可行性 (Effectiveness): 每一步都是可执行的。
时间复杂度与空间复杂度
我们用 大 O 表示法 (Big O Notation) 来衡量算法的优劣。
1. 时间复杂度 (Time Complexity)
衡量算法运行时间随数据规模 (\(n\)) 增长的变化趋势。
| 复杂度 | 名称 | 举例 | 说明 |
|---|---|---|---|
| \(O(1)\) | 常数阶 | 访问数组元素 arr[i] |
最快，与 \(n\) 无关 |
| \(O(\log n)\) | 对数阶 | 二分查找 | 每次减半，非常快 |
| \(O(n)\) | 线性阶 | 遍历数组 | 随 \(n\) 线性增长 |
| \(O(n \log n)\) | 线性对数阶 | 快速排序、归并排序 | 大多数高效排序的极限 |
| \(O(n^2)\) | 平方阶 | 冒泡排序、双重循环 | \(n=10^4\) 时通常超时 |
| \(O(2^n)\) | 指数阶 | 递归求解斐波那契 | 极慢，仅适用于极小 \(n\) |
| \(O(n!)\) | 阶乘阶 | 旅行商问题暴力解 | 最慢 |
2. 空间复杂度 (Space Complexity)
衡量算法在运行过程中临时占用的存储空间大小。
- \(O(1)\): 原地操作，不需要额外空间。
- \(O(n)\): 需要开辟一个长度为 \(n\) 的辅助数组。
- \(O(\log n)\): 递归调用栈的深度（如归并排序）。
算法评估技巧
在一般的算法竞赛或工程面试中，计算机 1 秒钟大约能执行 \(10^8\) (1 亿) 次基本运算。
- 若 \(N \le 10^6\)，算法最好是 \(O(n)\) 或 \(O(n \log n)\)。
- 若 \(N \le 10^4\)，算法可以是 \(O(n^2)\)。
- 若 \(N \le 20\)，算法可以是 \(O(2^n)\)。
常用数据结构回顾
算法离不开数据结构，选择合适的数据结构往往能将时间复杂度从 \(O(n^2)\) 降为 \(O(n \log n)\)。
- 数组 (Array): 随机访问 \(O(1)\)，插入删除 \(O(n)\)。
- 链表 (Linked List): 插入删除 \(O(1)\)，随机访问 \(O(n)\)。
- 栈 (Stack): 先进后出 (LIFO)，DFS 基础。
- 队列 (Queue): 先进先出 (FIFO)，BFS 基础。
- 哈希表 (Hash Map): 查找、插入、删除平均 \(O(1)\)。
- 堆 (Heap/Priority Queue): 始终能快速(\(O(1)\))获得最大/最小值。
下一章：模拟与枚举