最好情况分析

概述

最好情况分析 是对算法在最优输入下运行时间的下界分析，刻画算法性能的理论最优表现。

定义

最好情况运行时间

对于输入规模为 $n$ 的问题，算法在所有合法输入中运行时间最短的输入所对应的运行时间，记为 $T_{\text{best}}(n)$。

核心性质

• 最好情况时间复杂度给出算法运行时间的下界，即 $T(n)\ge T_{\text{best}}(n)$ 对所有输入成立。
• 最好情况通常不能代表算法的典型行为，实际意义有限。
• 即使最好情况为 $\Theta (1)$，算法的平均或最坏情况仍可能很慢（如线性搜索）。
• 最好情况分析需要显式构造使算法表现最优的输入实例。

章节扩展

第2章：入门

• 在 2.2 算法分析 中，CLRS 强调最坏情况分析和平均情况分析比最好情况分析更有实际意义。
• 插入排序的最好情况发生在输入已排序时，运行时间为 $\Theta (n)$。

参见

• 最坏情况分析
• 平均情况分析
• 渐近记号