正如我们可以看到不同算法的最佳、最差和平均情况时间复杂度，然后假设对于合并排序，最佳情况应该是 Ω(n logn)，但给出的却是 O(n logn)。类似地，对于平均情况，应该给出 θ(n logn)，但也使用大 O 表示法。而且这个大O符号在这个表中随处可见，无论是最佳情况还是平均情况。请解释一下原因。
最佳答案
实际上，使用了两种版本的渐近表示法。
形式化、数学上严格的渐近。如果您在数学环境中工作(例如，您试图证明某些表达式的严格界限，或者您试图论证为什么某种算法不存在)，那么您绝对需要从 O 中进行选择、Ω、o、ω、θ 等在论证过程中应正确使用，因为它们具有特定的技术含义。这就是为什么，例如，如果您拿起一篇计算机科学理论论文，您会看到各种不同的渐近符号的混合。
非正式、外行使用。大多数实践软件工程师都对大 O 表示法感兴趣，因为它与整体程序效率相关。在这种情况下，大 O 表示法的使用方式在技术上数学上并不正确，但仍然可以很好地表达其含义。例如，某人可能决定选择一个数据结构而不是另一个数据结构，理由是“对第一个数据结构的操作需要时间 O(log n)，而对第二个数据结构的操作需要时间 O(n)”，即使这样的语句是类似于这样说:“Amit 比 Pranav 矮，因为 Amit 最多 2m 高，Pranav 最多 5m 高。”尽管这在数学上并不正确，但从该术语经常被使用的方式来看，它的含义通常很清楚。
这些符号的挑战在于，如果您期望对算法的运行时间进行 super 严格、精确、数学上准确的描述，并且外行人会使用大 O 符号，那么您会感到困惑，因为它的字面含义所说的可能是错误的。同样，如果您是一名软件工程师，习惯了外行版本的大 O 表示法，而有人开始摆弄 θ 和 Ω 表示法，那么这可能会令人困惑，因为您可能不习惯看到它。
我认为对你的问题的“最佳”答案是“制作该表格的人可能应该使用更精确的渐近符号，因此即使从技术上讲他们所做的并不理想，但这是一种相对常见的做法信息以这种方式。”由于我倾向于在 Theoryland 上花费大量时间，因此我个人更希望他们在这里改用不同的渐近表示法，但由于我还与一群软件工程师打交道，所以我完全理解他们为什么不这样做。
关于sorting - 为什么我们在最佳和平均情况下也使用大 O 表示法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/51927486/