时间复杂度

时间复杂度刻画算法操作次数随输入规模增长的趋势。它基于抽象成本模型预测扩展性，但不能替代在真实硬件和数据集上的实测。

明确模型假设

在化简复杂度界限前，必须厘清以下前提：

• $n$ 的具体含义，或是否涉及 $V$（顶点数）、$E$（边数）等多参数；
• 哪些操作被视为常数时间（$O(1)$）；
• 分析的是最坏、平均、期望、摊还（Amortized），还是输出敏感（Output-sensitive）场景；
• 对数据表示、有序性、随机性及数值位宽的假设。

例如，基于邻接表的 BFS 复杂度是 $O(V+E)$，而非简单的 $O(V)$。若算法耗时与数值容量呈多项式关系，但相对于编码后的输入长度（如 $\log N$）呈指数关系，则称为伪多项式时间（Pseudo-polynomial）。

渐近记号

• $T(n)=O(f(n))$：最终上界。
• $T(n)=\Omega(f(n))$：最终下界。
• $T(n)=\Theta(f(n))$：紧确界（上下界匹配）。

Big-O 不等于“最坏情况”。渐近记号描述增长阶，情况分析描述输入分布，二者独立。例如，可以描述某算法的期望运行时间为 $\Theta(n\log n)$，或最坏情况上界为 $O(n^2)$。

分析模式

• 线性阶段相加：连续执行阶段的成本累加，通常由增长最快的项主导。
• 嵌套结构相乘：仅当内层操作在外层每一步都完整执行时，成本才相乘。
• 区间折半/倍增：通常导致对数级深度（$\log n$）。
• 递归分析：需建立递推关系（Recurrence）或使用会计法（Accounting Method）论证。
• 输出敏感：枚举类算法必须计入输出规模。生成 $n!$ 个排列，总时间复杂度不可能低于阶乘级。

常见增长阶

$$1 < \log n < n < n\log n < n^2 < c^n < n! \qquad(c>1)$$

上述排序为渐近意义下的比较。实际性能交叉点（Crossover Point）仍受常数因子、缓存命中率、向量化指令、内存分配策略及输入分布影响。

量词与实际计数

对于最终非负的函数，$T(n)=O(f(n))$ 表示存在常数 $c>0$、$n_0$，使所有 $n\geq n_0$ 都满足 $T(n)\leq c f(n)$。这些常数不能随 $n$ 增长。若 $T(n)=3n^2+2n+7$，则 $n\geq1$ 时有 $3n^2\leq T(n)\leq12n^2$，从而证明 $\Theta(n^2)$，不只是一个上界。

def pair_count(n):
    count = 0
    for i in range(n):
        for j in range(i):
            count += 1
    return count

assert pair_count(4) == 6
assert pair_count(0) == 0

对非负整数 n，内层循环体执行 $\sum_{i=0}^{n-1}i=n(n-1)/2$ 次。若内层变量改为从 1 开始，在小于 n 时不断翻倍，则 $n\geq1$ 时执行 $\lceil\log_2 n\rceil$ 次。外层每一步都完整重复这个内层循环，总共 $n$ 步，成本就是 $\Theta(n\log n)$，不能仅因有两层循环就判为 $\Theta(n^2)$。

最好、最坏、平均、期望与摊还

最好和最坏分别取同规模输入上的最小和最大成本。平均情况对明确的输入分布取期望。随机化算法的期望成本则对算法自身的随机选择取平均，可以针对任意固定输入；两者的随机性来源不同。

摊还成本不需要概率模型，它约束一串操作的总成本。考虑初始为空、容量从一开始、满时翻倍的动态数组。执行 $m$ 次追加时，扩容复制成本为 $1+2+4+\cdots<2m$，新元素写入成本为 $m$，总工作量为 $O(m)$，所以每次追加摊还 $O(1)$，尽管一次扩容可能需 $\Theta(m)$。追加八次时，共复制 $1+2+4=7$ 个槽位，新写入八个。若容量每次只增加一，就会复制 $1+2+\cdots+(m-1)$ 个槽位，失去常数摊还界限。这里统计的是引用槽位操作，不是任意精度整数运算、昂贵比较或实际延迟。

参考

• MIT OpenCourseWare: Asymptotic Complexity

我的阅读 · 打开过的笔记会记在当前浏览器里。