c - theta 表示法称为平均情况吗？

Question

有一些书说 theta 表示法称为平均情况，而另一些则说 theta 不是平均情况。如果theta不是平均情况，那么在算法方面什么叫平均情况？

Answer 1

O、Ω 和 Θ 符号实际上与算法的最佳/平均/最差情况无关。它们是表达函数渐近行为的方法，无论它们是什么。

f(n) = O(g(n)) 意味着 f 不会比 g 增长得更快。 g 是上界，紧与不紧。

f(n) = Ω(g(n)) 表示 f 的增长速度不慢于 g。 g 是一个下界，紧与不紧。

f(n) = Θ(g(n)) 表示 f 的增长速度与 g 一样快。 g 是上界和下界的紧界。

那么，算法的最佳/平均/最差运行时间是元素数​​量的函数，通常有 O、Ω、Θ 表示。

在对特定算法的分析中，人们通常能够推导出最坏情况的 O 界限，无论是否紧。此外，如果付出更多努力，平均时间会有所限制。通常您不关心最佳时间。

然后在给定问题的分析中(不管解决它的任何特定算法)，有时可以建立运行时间的绝对下限，这是最佳时间(紧或不紧)的 Ω 界限。平均时间的下限有时是可能的，但技术性很强。