数据结构与算法 / 知识点

数据结构与算法复杂度速查

算法选择

在 n 足够大时,通常按 O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ)、O(n!) 判断增长快慢;小规模时常数因子仍可能改变实际表现。

时间复杂度比较顺序

需要快速比较两个算法随输入规模增长时谁更容易失控,可先按渐进增长率排序;这个顺序适合做大规模输入下的第一轮筛选,但不能直接等同于真实运行时间。

怎么判读

复杂度 增长特征 常见判断动作
O(1) 工作量基本不随 n 增长 通常优先保留
O(log n) n 成倍增加时只增加少量步骤 很适合大规模输入
O(n) 工作量与输入规模近似成正比 通常可以接受
O(n log n) 比线性增长更快,但远低于平方级 常见于高效排序、分治算法
O(n²) n 翻倍时工作量约增至四倍 大输入前先估算规模上限
O(2ⁿ) 每增加一个规模单位都可能近似翻倍 只适合很小的 n 或需要剪枝、状态压缩
O(n!) 增长速度极快 通常只能处理极小规模

当 n 足够大时,常用增长顺序是 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。比较时先看增长阶,再看题目的最大输入规模是否会让操作次数进入不可接受区间。

容易误判的情况

相同 Big-O 不代表实际速度相同。例如两个 O(n) 算法可能分别执行约 2n 和 100n 次核心操作;在 n 较小时,常数因子、缓存局部性、函数调用和内存分配都可能主导结果。

反过来,小规模输入下一个 O(n²) 实现也可能暂时比复杂但常数较大的 O(n log n) 实现更快。因此复杂度排序回答的是增长趋势,不是某次运行的绝对耗时。

选择动作

先用最大输入规模排除明显不可行的增长阶,再在剩余方案中比较常数开销、额外空间、数据分布和实现复杂度。若两个方案复杂度相同,应通过基准测试或实际工作负载继续判断,而不是仅凭 Big-O 得出速度结论。

目录与阅读设置

记录一个想法

数据结构与算法复杂度速查

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通