Skip to main content

1 / 4概念

Complexity Analysis

复杂度分析回答的是“输入变大十倍,代价会变成多少”。它不是背 O(n log n),而是在写代码之前判断哪种实现值得写、在容量翻倍时系统会不会先崩。

1 概念​

1.1 一句话定义​

复杂度分析用输入规模 n 的函数描述算法消耗的时间或空间,并只保留增长最快的项。它关心的是 n → ∞ 时的渐进行为,不是某台机器上的绝对毫秒数。

1.2 它解决什么问题​

  • 选实现:同一问题有 O(n²) 和 O(n log n) 两种写法,先判断 n 的量级再决定是否值得优化。
  • 定容量:QPS 翻倍、数据量翻十倍时,先算增长阶,再做压测。
  • 找瓶颈:嵌套循环、重复扫描、隐式拷贝通常比“语言快不快”更致命。
  • 说清前提:最好/最坏/平均/摊还是四种不同承诺,不能混着用。

没有复杂度分析,团队只能用“跑得快”做决策;数据一涨,结论就失效。

1.3 不属于本页的内容​

主题去哪
排序、二分、图算法的具体流程Sorting & Searching、Graph Algorithms
数组、链表、树、哈希表的实现Linear Structures、Trees & Heaps、Graph Structures
P、NP、NP 完全性Computational Complexity
基准测试、profiler、火焰图性能测试与可观测性相关页面
摊还数据结构(并查集、动态数组)的实现Linear Structures、Graph Structures

1.4 关键术语​

术语含义容易混淆的点
输入规模 n决定代价的自变量不是“元素个数”永远;可能是位数、边数、矩阵维度
O渐进上界,忽略常数不是“精确运行时间”
Ω渐进下界不是“最好情况”
Θ渐进紧确界,上下界同阶不是“平均情况”
o / ω严格小于 / 严格大于与 O / Ω 差一个等号
最坏 / 平均 / 最好对输入分布的三种承诺平均不是“均匀分布”
摊还一串操作的平均代价不是概率期望
辅助空间除输入外额外占用的空间不是总内存
递归式用自身描述代价的方程不是所有递归都能用主定理
主定理解 T(n)=aT(n/b)+f(n) 的工具有适用条件,不是万能公式