big-o - 为什么从未使用 theta 表示法？

Question

我正在攻读计算机科学学位，在课堂上我们使用 big-theta 表示法比 big-O 表示法更频繁。尽管在阅读有关算法及其运行时间的文章时，我几乎找不到任何地方的大θ符号。在大多数书籍和文章中，为什么不使用 theta 表示法以更合适的方式指示算法运行时间的最坏情况？

Answer 1

• Big-O 是一个上限。

• Big-Theta 是一个紧界，即上限和下限。

当人们只担心可能发生的最坏情况时，big-O 就足够了；即它说“它不会比这更糟”。当然，界限越紧越好，但严格的界限并不总是容易计算[1]。

---

下面的观点[2]会让你更好的理解：

正如人们所说，big-Theta 是一个双边界限。严格来说，当你想解释一个算法可以做得多么好，或者那个算法不能做得更好或者没有算法可以做得更好时，你应该使用它。例如，如果您说“排序需要对最坏情况输入进行 Θ(n(log n)) 比较”，那么您是在解释有一种排序算法对任何输入使用 O(n(log n)) 比较; 并且对于每个排序算法，都有一个输入迫使它进行 Ω(n(log n)) 比较。

现在，人们使用 O 而不是 Ω 的一个狭隘原因是放弃关于最坏或平均情况的免责声明。如果您说“排序需要 O(n(log n)) 比较”，那么该语句仍然适用于有利的输入。另一个狭隘的原因是，即使一个算法做 X 需要时间 Θ(f(n))，另一种算法可能做得更好，所以你只能说 X 本身的复杂度是 O(f(n))。

然而，人们非正式地使用 O 有一个更广泛的原因。在人类层面上，当相反的一面从上下文中“显而易见”时，总是做出两面的陈述是一种痛苦。由于我是一名数学家，理想情况下我会始终小心地说“当且仅当下雨时我会带伞”或“我可以玩 4 个球但不能玩 5 个”，而不是“如果下雨我会带伞”下雨”或“我可以玩 4 个球”。但是这些陈述的另一半通常是明显有意或明显无意的。对显而易见的事情马虎是人的天性。把头发分开是令人困惑的。

不幸的是，在数学或算法理论等严格的领域，不分叉也会让人困惑。当人们应该说Ω或Θ时，人们不可避免地会说O。因为“显而易见”而跳过细节总是会导致误解。没有解决方案。