为什么我们使用大O符号表示最佳和平均情况呢？

Question

我们可以看到不同算法的最佳，最差和平均时间复杂度，然后假设合并排序，最佳情况应该是Ω（n logn），而是给定O（n logn）。类似地，对于平均情况，它应该被赋予Θ（n logn）但是也使用大O符号。无论是最佳情况还是普通情况，这个大O符号在本表中随处可见。请解释一下原因。

Answer 1

在实践中，有两种版本的渐近符号在使用中。

• 正式的，数学上严格的渐近性。如果你在一个数学环境中工作（例如，你试图证明某个表达式的严格界限，或者你试图争论为什么某个算法不存在），那么你绝对需要从O中选择，Ω，o，ω，Θ等在进行论证的过程中是正确的，因为它们具有特定的技术含义。这就是为什么，例如，如果你拿起CS理论论文，你会看到一系列不同的渐近符号被抛出。
• 非正式，非专业用法。大多数执业软件工程师都对big-O符号感兴趣，因为它与整体程序效率有关。在这种情况下，big-O表示法的使用方式在技术上并非在数学上正确，但仍然是一个很好的代理。例如，某人可能决定选择一个数据结构而不是另一个数据结构，其理由是“第一个数据结构上的操作需要时间O（log n），而第二个数据结构上的操作需要时间O（n）”，即使这样的语句是类似于说“Amit比Pranav短，因为Amit最多2米高，Pranav最多5米高。”虽然这在数学上并不正确，但通常在这个术语被抛出的方式上通常很清楚它是什么意思。

这些符号的挑战在于，如果您期望对算法的运行时进行超级严格，精确，数学上准确的描述，并且您使用了大O符号，那么您会感到困惑，因为所说的可能的字面含义可能会是错的。同样，如果你是一个软件工程师，他已经习惯了外行版的big-O表示法而且有人开始使用Θ和Ω表示法，那可能会让人感到困惑，因为你可能不习惯看到它。

我认为你问题的“最佳”答案是“制作该表的人可能应该使用更精确的渐近符号，所以即使从技术上讲他们所做的事情并不理想，但以这种方式呈现信息是一种相对普遍的做法。 “。由于我倾向于在Theoryland上花费大量时间，所以我个人更喜欢在这里使用不同的渐近符号，但由于我还与一群软件工程师交互，我完全理解为什么他们没有。