大O表示法具体含义总结表
时间复杂度详解
| 大O表示 | 名称 | 含义 | 示例 | 增长曲线 | 执行时间(n=1000)假设 |
|---|---|---|---|---|---|
| O(1) | 常数时间 | 执行时间不随输入规模变化 | 数组索引访问、哈希表查找 | 水平线 | 1单位时间 |
| O(log n) | 对数时间 | 执行时间随输入规模对数增长 | 二分查找、平衡树操作 | 缓慢上升曲线 | 10单位时间 |
| O(√n) | 平方根时间 | 执行时间随输入规模的平方根增长 | 某些数论算法、质数检查 | 平缓上升 | 31.6单位时间 |
| O(n) | 线性时间 | 执行时间与输入规模成正比 | 数组遍历、线性搜索 | 45°直线 | 1000单位时间 |
| O(n log n) | 线性对数时间 | 执行时间 = n × log n | 高效排序算法(快速排序、归并排序) | 略高于线性 | 10000单位时间 |
| O(n²) | 二次时间 | 执行时间与输入规模的平方成正比 | 简单排序(冒泡、选择)、嵌套循环 | 快速上升曲线 | 1,000,000单位时间 |
| O(n³) | 立方时间 | 执行时间与输入规模的立方成正比 | 三重嵌套循环、某些矩阵运算 | 急剧上升 | 1,000,000,000单位时间 |
| O(2ⁿ) | 指数时间 | 执行时间呈指数增长 | 暴力破解、汉诺塔递归 | 急剧爆炸增长 | 1.07×10³⁰¹单位时间 |
| O(n!) | 阶乘时间 | 执行时间呈阶乘增长 | 旅行商问题暴力解、全排列 | 极端爆炸增长 | 4×10²⁵⁶⁷单位时间 |
复杂度等级对比表
| 复杂度 | n=10 | n=100 | n=1000 | n=10000 | 实用性 |
|---|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 1 | 优秀 |
| O(log n) | 3.3 | 6.6 | 10 | 13.3 | 优秀 |
| O(√n) | 3.2 | 10 | 31.6 | 100 | 良好 |
| O(n) | 10 | 100 | 1000 | 10000 | 良好 |
| O(n log n) | 33 | 664 | 9966 | 132877 | 可接受 |
| O(n²) | 100 | 10000 | 10⁶ | 10⁸ | 小型数据可用 |
| O(n³) | 1000 | 10⁶ | 10⁹ | 10¹² | 仅限极小数据 |
| O(2ⁿ) | 1024 | 1.27×10³⁰ | 巨大 | 天文数字 | 不可用 |
| O(n!) | 3628800 | 9.33×10¹⁵⁷ | 巨大 | 天文数字 | 完全不可用 |
空间复杂度详解
| 大O表示 | 名称 | 含义 | 示例 |
|---|---|---|---|
| O(1) | 常数空间 | 算法使用固定大小的额外空间 | 原地排序、简单变量 |
| O(log n) | 对数空间 | 额外空间随输入规模对数增长 | 递归算法的调用栈(如快速排序) |
| O(n) | 线性空间 | 额外空间与输入规模成正比 | 创建新数组、哈希表存储 |
| O(n log n) | 线性对数空间 | 额外空间 = n × log n | 某些递归算法 |
| O(n²) | 二次空间 | 额外空间与输入规模的平方成正比 | 创建二维数组、邻接矩阵 |
常见算法的具体数值含义
排序算法示例
// O(n²): 冒泡排序 for (let i = 0; i < n; i++) { // n次 for (let j = 0; j < n - i - 1; j++) { // 平均n/2次 // 比较操作: 总共 ≈ n²/2 次 } } // 实际执行次数: 约 0.5n² 次比较 // O(n log n): 快速排序 // 每次递归将数组分成两半: log n 层 // 每层处理所有元素: n 次操作 // 总操作: n × log n搜索算法示例
// O(log n): 二分查找 // 每次将搜索范围减半 // 查找次数 = log₂n // 例如: n=1024 → 最多10次查找 // n=100万 → 最多20次查找 // O(n): 线性查找 // 最坏情况: 查找整个数组 // 查找次数 = n
实际性能参考表
| 操作数量级 | 可接受算法复杂度 | 1GHz CPU处理时间估计 |
|---|---|---|
| n ≤ 100 | O(n³), O(2ⁿ) (小规模) | < 1秒 |
| 100 < n ≤ 10,000 | O(n²) | 1秒 - 几分钟 |
| 10,000 < n ≤ 1,000,000 | O(n log n) | 几秒 - 几分钟 |
| n > 1,000,000 | O(n), O(log n), O(1) | 几秒 - 几分钟 |
| n > 10⁹ | O(log n), O(1) | 实时或近实时 |
重要注意事项
大O表示法忽略常数因子: O(100n) 仍写作 O(n)
关注最坏情况: 大O通常表示最坏情况复杂度
实际性能受多种因素影响:
硬件性能
编程语言效率
算法具体实现
输入数据的特性
复杂度对比的实际意义:
O(n) 比 O(n log n) 好10倍以上时，n通常 > 1000
O(log n) 在大数据时优势明显
常数因子在n较小时可能起决定性作用
选择算法的指导原则
n < 10: 简单算法即可，复杂度不重要
10 < n < 1000: 避免O(n³)和更差的算法
1000 < n < 10⁶: 优先选择O(n log n)或更好的算法
n > 10⁶: 必须使用O(n)或更优算法
记住：大O表示法帮助我们理解算法随数据规模增长的趋势，但在实际开发中需要结合具体场景和性能测试来选择最合适的算法。
JavaScript 常见算法复杂度总结（大O表示法）
以下是JavaScript中常见算法的时间与空间复杂度总结：
时间复杂度表
| 算法类型 | 最佳情况 | 平均情况 | 最坏情况 | 常见示例 |
|---|---|---|---|---|
| 常数时间 | O(1) | O(1) | O(1) | 数组索引访问、对象属性访问 |
| 对数时间 | O(1) | O(log n) | O(log n) | 二分查找、平衡二叉搜索树操作 |
| 线性时间 | O(n) | O(n) | O(n) | 数组遍历、线性搜索 |
| 线性对数时间 | O(n) | O(n log n) | O(n log n) | 快速排序、归并排序、堆排序 |
| 二次时间 | O(n) | O(n²) | O(n²) | 冒泡排序、选择排序、插入排序 |
| 指数时间 | O(1) | O(2ⁿ) | O(2ⁿ) | 汉诺塔、斐波那契递归解法 |
| 阶乘时间 | O(1) | O(n!) | O(n!) | 旅行商问题暴力解法 |
空间复杂度表
| 算法类型 | 空间复杂度 | 描述 |
|---|---|---|
| 原地算法 | O(1) | 不使用额外空间或使用常量空间 |
| 线性空间 | O(n) | 额外空间与输入大小成正比 |
| 递归算法 | O(n) | 递归调用栈的空间消耗 |
JavaScript常见算法具体分析
1. 搜索算法
| 算法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 线性搜索 | O(n) | O(1) | 遍历数组查找元素 |
| 二分搜索 | O(log n) | O(1) | 要求数组已排序 |
| 深度优先搜索(DFS) | O(V+E) | O(V) | 图/树遍历，V为顶点数，E为边数 |
| 广度优先搜索(BFS) | O(V+E) | O(V) | 图/树遍历 |
2. 排序算法
| 算法 | 最佳 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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) | 不稳定 |
3. 数据结构操作
| 数据结构 | 访问 | 搜索 | 插入 | 删除 | 空间复杂度 |
|---|---|---|---|---|---|
| 数组 | O(1) | O(n) | O(n) | O(n) | O(n) |
| 栈/队列 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 链表 | O(n) | O(n) | O(1) | O(1) | O(n) |
| 哈希表 | O(1)* | O(1)* | O(1)* | O(1)* | O(n) |
| 二叉搜索树 | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) |
注：带号表示平均情况，最坏情况可能退化*
实际应用建议
小数据集(n < 100)：简单算法(如冒泡排序)可能更合适
中型数据集(n < 10,000)：使用O(n log n)算法如快速排序
大型数据集(n > 10,000)：优先考虑O(n log n)或O(n)算法
内存敏感场景：选择原地算法(空间复杂度O(1))
需要稳定排序：选择归并排序或插入排序
JavaScript内置方法复杂度
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
Array.prototype.push/pop | O(1) | 数组末尾操作 |
Array.prototype.shift/unshift | O(n) | 数组开头操作，需要重新索引 |
Array.prototype.sort | O(n log n) | V8引擎使用TimSort(归并+插入) |
Array.prototype.includes/indexOf | O(n) | 线性搜索 |
Array.prototype.slice | O(n) | 需要复制元素 |
Object.keys/values/entries | O(n) | 遍历对象属性 |
记住：大O表示法描述的是算法性能随输入规模增长的趋势，实际性能还受常数因子、硬件特性、JavaScript引擎优化等因素影响。
