最好最坏平均时间复杂度 · 融合风（象牙 + Obsidian 入口）

速查

同一算法在不同输入下执行时间差异大，需区分三种情况：最好 $T_{\text{best}}(n)$（最优输入最少次数）、最坏 $T_{\text{worst}}(n)$（最差输入最多次数，最常用、作性能上限）、平均 $T_{\text{avg}}(n)$（等概率期望）。均摊分析则看一系列操作的平均代价。

概述 ▾

同一算法在不同输入下的执行时间可能差异很大，因此需要区分三种情况来刻画性能：

最好时间复杂度：最优输入下执行基本操作的最少次数。如顺序查找最好情况是第一个就找到，$T_{\text{best}}(n) = O(1)$。
最坏时间复杂度：最差输入下执行基本操作的最多次数。如顺序查找最坏情况是最后一个才找到或找不到，$T_{\text{worst}}(n) = O(n)$。
平均时间复杂度：所有输入等概率下执行次数的数学期望。如顺序查找平均比较 $\frac{n+1}{2}$ 次，$T_{\text{avg}}(n) = O(n)$。

均摊分析分析一系列操作的总代价再除以操作次数。如动态数组扩容：单次 push 可能 $O(n)$ 复制，但 $n$ 次 push 总代价 $O(n)$，均摊每次 $O(1)$。

核心概念 ▾

均摊分析（Amortized Analysis）：分析一系列连续操作的总代价再除以操作次数。单次操作可能很贵，但平均下来很便宜。它针对的是"操作的序列"，与针对"单次操作不同输入"的平均情况不同。

例：动态数组（如 C++ vector）在容量满时扩容为 2 倍并复制。设第 $i$ 次扩容复制 $2^{i-1}$ 个元素，则 $n$ 次 push 的总复制代价为 $1+2+4+\dots+2^{\lceil\log_2 n\rceil} = O(n)$，均摊到每次 push 为 $O(1)$。

关键性质 ▾

复杂度类型	含义	分析依据	用途
最好 $T_{\text{best}}$	最优输入的代价	下界	了解算法最佳性能
最坏 $T_{\text{worst}}$	最差输入的代价	上界	保证性能上限，最常用
平均 $T_{\text{avg}}$	所有输入的期望代价	概率加权	反映实际表现
均摊 $T_{\text{amortized}}$	一系列操作的平均代价	总代价/操作数	分析连续操作效率

常见考法 ▾

命题套路给定算法求三种复杂度、判断"$O(n)$ 是最坏还是平均"、比较不同算法在各情况的表现、计算均摊代价。

考法	解题套路
求最好/最坏/平均	找最好输入（最少比较）与最坏输入（最多比较）
判断说法正误	"$O(n)$ 是最坏"→正确；"是平均"→需具体分析
比较不同算法	列表对比各算法在三种情况下的复杂度
均摊分析	算 $n$ 次操作总代价，再除以 $n$

易错点 ▾

必记

"时间复杂度"默认指最坏情况：除非特别说明，一般指最坏时间复杂度。
最好 $O(1)$ 不代表算法快：如快排最好 $O(n\log n)$，但特定输入会触发最坏 $O(n^2)$。
平均情况不是"中间情况"：它是数学期望，需要考虑所有输入的概率分布。
均摊 $\neq$ 平均：均摊针对一系列操作，平均针对单次操作的不同输入。
最坏不是"不可能发生"：快排在已排序数组用首元素作枢轴必然触发最坏。

核心结论 ▾

工程中最坏时间复杂度最重要——它保证性能上限。
顺序查找：最好 $O(1)$，最坏 $O(n)$，平均 $O(n)$。
快速排序：最好 $O(n\log n)$，最坏 $O(n^2)$，平均 $O(n\log n)$。
冒泡排序：最好 $O(n)$（已排序+优化），最坏 $O(n^2)$，平均 $O(n^2)$。
归并排序三者始终 $O(n\log n)$。

记忆卡片 ▾

默认的"时间复杂度"指哪种？

最坏时间复杂度。

顺序查找的三种复杂度？

最好 $O(1)$，最坏 $O(n)$，平均 $O(n)$。

快排最好/最坏/平均？

$O(n\log n)$ / $O(n^2)$ / $O(n\log n)$。

均摊与平均的区别？

均摊针对操作序列，平均针对单次操作的不同输入。

归并排序三种复杂度？

都是 $O(n\log n)$。

快排何时必触发最坏？

已排序数组用首元素作枢轴。

交互动画 · 三种复杂度的对比 ▾

选择一个算法，对比它的最好 / 最坏 / 平均时间复杂度

柱长按量级示意

概述 ▾

核心概念 ▾

关键性质 ▾

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 三种复杂度的对比 ▾

相关知识点