算法是解决特定问题的一系列明确步骤。算法的五大特性:
用大O记号表示算法的时间开销与输入规模的关系。
常见复杂度(从快到慢):
$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$
衡量算法运行过程中临时占用存储空间大小的度量。
| 算法思想 | 核心思路 | 典型应用 |
|---|---|---|
| 枚举 | 逐一尝试所有可能 | 密码破解、简单搜索 |
| 贪心 | 每步取局部最优 | 活动安排、找零问题 |
| 分治 | 分解→解决→合并 | 归并排序、快速排序 |
| 递推/递归 | 利用子问题的解 | 斐波那契、阶乘 |
| 搜索 | DFS/BFS遍历状态空间 | 迷宫问题 |
| 动态规划 | 记忆化避免重复计算 | 背包问题 |
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
