算法的时间复杂度分析 · 融合风（象牙 + Obsidian 入口）

速查

时间复杂度衡量基本操作的执行次数随 $n$ 的增长趋势。大 O 表示法 $T(n) = O(f(n))$：只保留最高阶项、忽略系数。常见顺序 $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)$。

概述 ▾

时间复杂度衡量算法的执行时间随问题规模增长的变化趋势。由于精确执行时间依赖硬件环境，我们用基本操作的执行次数来衡量。

大 O 表示法定义：若存在正常数 $c$ 和 $n_0$，当 $n \geq n_0$ 时 $T(n) \leq c\cdot f(n)$，则 $T(n) = O(f(n))$。

$$T(n) = O(f(n)) \iff \exists\, c>0,\ n_0>0,\ \forall n \geq n_0:\ T(n) \leq c\cdot f(n)$$

分析步骤：① 找出基本操作（最深层循环中的操作）；② 计算执行次数 $T(n)$；③ 只保留最高阶项、去系数；④ 写 $T(n)=O(f(n))$。

常见时间复杂度从小到大：

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$$

递归算法用递推方程分析，如 $T(n)=2T(n/2)+O(n) \Rightarrow O(n\log n)$；$T(n)=T(n/2)+O(1) \Rightarrow O(\log n)$。

复杂度	名称	$n=10^6$ 时量级	典型算法
$O(1)$	常数	1	数组按下标访问
$O(\log n)$	对数	20	折半查找
$O(n)$	线性	$10^6$	遍历数组
$O(n\log n)$	线性对数	$2\times10^7$	快速排序（平均）
$O(n^2)$	平方	$10^{12}$	冒泡排序
$O(2^n)$	指数	极大	穷举所有子集

命题套路求代码段复杂度（数循环）、递归复杂度（列递推）、比较算法、判断复杂度是否相同（$O(2n+3)=O(n)$）。

考法	解题套路
求代码段复杂度	单层 $O(n)$，双层嵌套 $O(n^2)$，折半 $O(\log n)$
递归复杂度	列递推方程，如 $T(n)=2T(n/2)+O(n)\Rightarrow O(n\log n)$
比较算法	将复杂度代入具体 $n$ 值比较大小
是否相同	系数和低阶项不影响，$O(2n+3)=O(n)$

必记

大 O 核心规则？

只保留最高阶项，忽略系数。

$n\times n$ 嵌套循环？

$O(n^2)$。

折半查找复杂度？

$O(\log n)$。

$O(n)$ 与 $O(n^2)$ 差？

$n$ 倍，$n$ 越大差距越大。

递推 $T=2T(n/2)+n$？

$O(n\log n)$。

常见复杂度排序？

$O(1)

点击一种复杂度，单独查看其增长曲线（曲线已按量级示意归一化）

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2)$