时间戳

首页 > 解决方案 > 为什么我们也使用大 O 表示法来表示最佳和平均情况？

sorting - 为什么我们也使用大 O 表示法来表示最佳和平均情况？

问题描述

这里

正如我们可以看到不同算法的最佳、最差和平均情况时间复杂度，然后假设对于归并排序，最佳情况应该是 Ω(n logn)，但它却是 O(n logn)。同样，对于一般情况，应该给定 Θ(n logn)，但也使用大 O 表示法。并且这个大 O 表示法在这个表中无处不在，无论是最佳情况还是平均情况。请解释一下为什么。

标签： sortingdata-structurestime-complexitybig-o

解决方案

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

  • 正式的、数学上严格的渐近线。如果你在数学环境中工作（例如，你试图证明某个表达式的严格界限，或者你试图争论为什么某个算法不存在），那么你绝对需要从 O , Ω, o, ω, Θ 等在论证过程中正确使用，因为它们具有特定的技术含义。这就是为什么，例如，如果你拿起一篇 CS 理论论文，你会看到混合了不同的渐近符号。

  • 非正式的、外行的用法。大多数执业软件工程师都对大 O 表示法感兴趣，因为它与整体程序效率有关。在这种情况下，使用大 O 表示法的方式在技术上数学上并不正确，但仍然可以很好地代表含义。例如，有人可能决定选择一个数据结构而不是另一个数据结构，理由是“第一个数据结构上的操作需要时间 O(log n)，而第二个数据结构上的操作需要时间 O(n)”，即使这样的陈述是类似于说“Amit 比 Pranav 短，因为 Amit 最多 2m 高，Pranav 最多 5m 高”。虽然这在数学上并不正确，但这个术语通常被抛出，通常很清楚它的含义。

这些符号的挑战在于，如果您期望对算法的运行时间进行超级严格、精确、数学上准确的描述，并且您得到一个外行使用大 O 符号，您会感到困惑，因为所说内容的字面意思可能是错的。同样，如果您是一名软件工程师，并且习惯了大 O 表示法的外行版本，并且有人开始折腾 Θ 和 Ω 表示法，那可能会令人困惑，因为您可能不习惯看到它。

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

推荐阅读