渐近时间复杂度与最优/平均/最坏场景组合的合理性及应用问询

核心误区澄清 #

首先你听到的「渐近表示法与最优、平均、最坏情况无关」的说法没有错，但被很多人误读了：这句话指的是O/Ө/Ω本身是描述函数增长趋势的纯数学工具，本身不默认绑定任何输入场景，而不是说两者不能组合。

两类概念是完全正交的关系：

• 渐近符号（O/Ө/Ω）：定义的是「函数的增长边界属性」，上界/紧界/下界都是对函数本身的数学描述
• 最优/平均/最坏场景：定义的是「你要分析哪一类输入对应的运行时间函数」，是你选择分析对象的维度

所以你列的9种组合，从数学定义上全部都是合理的，没有任何冗余或矛盾，只是大部分组合没有实际使用价值而已。

常用的组合说明 #

常规算法分析中只会用到以下几类组合，剩下的几乎不会出现：

• 最坏场景的O(...)：是最通用的默认标准，所有算法教材里没有特殊标注的「时间复杂度为O(f(n))」，默认指的就是最坏输入的上界，它给出了算法运行时间的最保守保证，无论输入什么数据，运行速度都不会慢于这个边界。
• 平均场景的O(...)/Ө(...)：次常用，用来描述算法在实际大部分输入下的表现，比如快速排序的平均复杂度为Ө(nlogn)，比最坏界更贴近真实使用体验。
• 最坏场景的Ө(...)：当某算法最坏输入的上下界一致时使用，比只给出上界O更准确，比如归并排序的最坏复杂度为Ө(nlogn)。
• 最坏场景的Ω(...)：一般只用于算法下界证明，比如「基于比较的排序算法最坏复杂度下界为Ω(nlogn)」，用来证明某类问题不可能存在比这个边界更快的通用解法。

几乎不使用的组合 #

剩下的组合没有实际参考价值，几乎不会出现在正式分析中：

• 所有最优场景的渐近界：最优输入是极其特殊的个例，知道算法最快能跑多快对实际使用和性能评估没有意义，比如冒泡排序最优输入的复杂度为Ө(n)，这个结论几乎没有应用场景。
• 平均场景的Ω(...)：我们分析平均场景的核心目的是得到平均运行速度的上界保证，下界没有实用价值。

内容的提问来源于stack exchange，提问作者Robin Andrews