最坏情况分析

概述

最坏情况分析 是对给定输入规模的所有可能输入，取最大运行时间的分析方法。它提供了算法性能的最坏情况保证，是CLRS中默认的算法分析方式。

定义

最坏情况分析

对于输入规模为 $n$ 的算法，最坏情况运行时间定义为： $T_{\text{worst}}(n)=\max \{T(n,I)\mid I\in {\mathcal{I}}_n\}$ 其中 ${\mathcal{I}}_n$ 是所有规模为 $n$ 的合法输入的集合，$T(n,I)$ 是算法在输入 $I$ 上的运行时间。

核心性质

• 保证性：最坏情况分析给出性能的下限保证，即算法的运行时间不会超过此值。
• 实用性：对于实时系统、安全关键系统等场景，最坏情况性能是最重要的指标。
• 与平均情况的区别：平均情况分析需要假设输入的概率分布，而最坏情况分析不需要任何概率假设。
• CLRS的默认选择：CLRS通常使用最坏情况运行时间作为算法效率的主要度量。
• 有时最坏情况分析可能过于悲观，某些算法的最坏情况很少出现（如快速排序的最坏情况 $\Theta (n^2)$ vs. 平均情况 $\Theta (n\lg n)$）。

章节扩展

第2章：入门

• 2.2 算法分析：以插入排序为例进行最坏情况分析。当输入为逆序排列时，每次内层循环都需要比较到子数组的最前端，总比较次数为 ${\sum }_{j=2}^{n}j=\Theta (n^2)$。

参见

• 运行时间
• 时间复杂度
• 增长量级
• RAM模型