算法复杂度是一个用于分析和比较算法效率的框架。它有助于衡量算法性能随输入大小增长的变化，这对于构建高效的软件系统至关重要。本页涵盖了渐近分析、大 O 符号的基础知识，以及如何在评估算法性能时应用这些概念。
理解算法复杂度使软件工程师能够
渐近分析通过衡量执行时间和内存使用随输入大小增加的增长情况来衡量算法效率。我们分析的是资源消耗的增长率，而不是测量绝对时间（这会因硬件而异）。
图：算法分析方法
渐近分析的关键概念
大 O 符号描述了算法增长率的上限（最坏情况）。它表示为 O(f(n))，其中 f(n) 是输入大小 n 的函数。
| 符号 | 姓名 | 描述 | 示例 |
|---|---|---|---|
| O(1) | 常量 | 执行时间与输入大小无关 | 数组访问，哈希表查找（最佳情况） |
| O(log n) | 对数级 | 执行时间随输入大小呈对数增长 | 二分查找，平衡二叉查找树 |
| O(n) | 线性级 | 执行时间随输入大小呈线性增长 | 线性查找，遍历数组 |
| O(n log n) | 线性对数 | 线性增长和对数增长的组合 | 高效排序算法（归并排序，快速排序平均情况） |
| O(n²) | 平方级 | 执行时间随输入大小的平方增长 | 冒泡排序，插入排序，嵌套循环 |
| O(n³) | 立方 | 执行时间随输入大小的立方增长 | 一些矩阵操作，朴素的三维计算 |
| O(2^n) | 指数级 | 执行时间随每个附加输入元素呈指数增长 | 斐波那契数列的递归计算，暴力解法 |
| O(n!) | 阶乘 | 执行时间随输入大小呈阶乘增长 | 暴力旅行商问题，生成所有排列 |
图：常见时间复杂度类别的层级结构（性能越好排在越上方）
来源：README.md589
虽然大 O 符号是最常用的符号，但还有其他重要的渐近符号
大 Ω (Omega)：下界符号。描述最佳情况。
大 Θ (Theta)：紧密界符号。描述算法的上限和下限相同的情况。
小 o (little-o)：严格上界。与大 O 类似，但排除了边界情况。
图：渐近符号之间的关系
分析算法复杂度时，请遵循以下规则
系数规则：忽略常数系数
求和规则：将独立操作的复杂度相加
乘积规则：将相关操作的复杂度相乘
多项式规则：保留最高次幂项
对数底数规则：对数底数在大 O 中无关紧要
理解标准操作和算法的复杂度至关重要
图：常见数据结构操作及其复杂度
| 算法 | 最佳情况 | 平均情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) |
空间复杂度衡量算法使用的内存量，与输入大小相关。它遵循与时间复杂度相同的大 O 符号。
空间复杂度的关键组成部分
常见空间复杂度
图：空间复杂度分析的组成部分
摊还分析检查一系列操作的平均性能，即使某些单个操作可能代价高昂。
这对于动态数组（向量）等数据结构尤为重要，因为偶尔的重新分配操作虽然昂贵但很少发生。
示例：向动态数组添加元素
来源：README.md585
在技术面试中，算法复杂度分析对于展示您的工程严谨性和解决问题能力至关重要。
最佳实践
该仓库推荐了几个学习算法复杂度的资源
所有这些资源都有助于建立对如何分析和比较基于资源使用模式的算法的扎实理解。
算法复杂度是计算机科学中的一个基本概念，它允许工程师分析、比较和优化算法。通过理解大 O 符号和渐近分析，您可以更好地预测您的代码在不同输入大小下的表现，并就算法和数据结构的选择做出明智的决策。
这些知识在技术面试中尤其有价值，因为展示对算法效率的理解可以显著影响您的成功。在您继续学习数据结构和算法时，请始终如一地应用复杂度分析，以培养对不同方法性能特征的直觉。