目录
- 复杂度基础概念
- 时间复杂度详解
- 空间复杂度详解
- 常见算法时间复杂度示例
- 常见数据结构操作时间复杂度
- 复杂度计算技巧与常见误区
- 总结
1️⃣ 复杂度基础概念
- 时间复杂度（Time Complexity）：算法执行所需时间与输入规模之间的关系，通常用大O符号表示，反映算法的运行效率。
- 空间复杂度（Space Complexity）：算法执行过程中占用的额外内存空间与输入规模的关系。
2️⃣ 时间复杂度详解
常见时间复杂度类型
| 复杂度 | 描述 | 示例 | 说明 |
|---|
| O(1) | 常数时间 | 访问数组元素 | 不随输入规模变化 |
| O(log n) | 对数时间 | 二分查找 | 每步减少问题规模一半 |
| O(n) | 线性时间 | 顺序遍历数组 | 需访问每个元素 |
| O(n log n) | 线性对数时间 | 归并排序、快速排序 | 排序类最优时间复杂度 |
| O(n²) | 平方时间 | 嵌套循环两层 | 双重循环遍历 |
| O(n³) | 立方时间 | 三重嵌套循环 | 三层嵌套循环 |
| O(2^n) | 指数时间 | 斐波那契递归（朴素） | 输入规模每增加1，时间翻倍 |
| O(n!) | 阶乘时间 | 全排列问题 | 计算量极大，规模稍大即难以计算 |
3️⃣ 空间复杂度详解
- 通常统计辅助空间，不包括输入本身所占空间。
- 例如递归调用栈空间也计入空间复杂度。
- 典型空间复杂度示例：
| 复杂度 | 说明 | 示例 |
|---|
| O(1) | 常数空间 | 变量个数固定 |
| O(n) | 线性空间 | 额外数组或链表存储 |
| O(n²) | 二维数组存储 | 矩阵相关算法 |
| O(log n) | 递归调用栈空间 | 二分查找递归 |
4️⃣ 常见算法时间复杂度示例
| 算法 | 时间复杂度 | 说明 |
|---|
| 线性搜索 | O(n) | 顺序遍历查找 |
| 二分查找 | O(log n) | 排序数组中折半查找 |
| 冒泡排序 | O(n²) | 双重嵌套循环比较交换 |
| 快速排序 | 平均 O(n log n) | 分治递归排序 |
| 归并排序 | O(n log n) | 分治归并排序 |
| 插入排序 | 最坏 O(n²)，最好O(n) | 插入有序部分，依赖输入数组近似有序程度 |
| 斐波那契递归 | O(2^n) | 重复计算子问题 |
| 动态规划（斐波那契） | O(n) | 记忆化避免重复计算 |
5️⃣ 常见数据结构操作时间复杂度
| 数据结构 | 插入 | 删除 | 查找 | 访问 |
|---|
| 数组 | O(n) | O(n) | O(n) | O(1) |
| 链表 | O(1)* | O(1)* | O(n) | O(n) |
| 栈 | O(1) | O(1) | O(n) | O(n) |
| 队列 | O(1) | O(1) | O(n) | O(n) |
| 哈希表 | O(1)均摊 | O(1)均摊 | O(1)均摊 | 不适用 |
| 二叉搜索树（平均） | O(log n) | O(log n) | O(log n) | 不适用 |
| 二叉搜索树（最坏） | O(n) | O(n) | O(n) | 不适用 |
| 堆 | O(log n) | O(log n) | O(n) | 不适用 |
* 链表插入和删除时间复杂度O(1)是基于已知节点指针。
6️⃣ 复杂度计算技巧与常见误区
- 忽略常数项和低阶项，如 O(2n)简化为 O(n)。
- 递归复杂度分析，可用递推关系和主定理解决。
- 区分最好、平均、最坏情况复杂度。
- 空间复杂度一般指额外开销，不包含输入本身。
- 注意数据结构操作细节，实际性能也受常数因子影响。
7️⃣ 总结
- 时间复杂度和空间复杂度是评价算法优劣的重要指标。
- 不同算法和数据结构对应不同复杂度，选择时需权衡。
- 理解复杂度有助于写出高效代码，避免性能瓶颈。
- 建议多用实例练习计算复杂度，结合代码理解。
发表回复