基础算法概念
知识总结
什么是算法
算法是解决特定问题的一系列明确步骤。算法的五大特性：
- 有穷性：算法必须在有限步骤后终止
- 确定性：每一步必须有明确的定义
- 可行性：每一步都可以通过有限次基本运算实现
- 输入：有零个或多个输入
- 输出：有一个或多个输出
时间复杂度
用大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) | 稳定 |