运行时间：界限与情况

Question

注意：请不要将此标记为作业！我不是学生，这也不是一个任务。我是一名软件工程师，正在整理我旧的数据结构和算法教材，并试图回忆多年前学到的东西，但好像在网上找不到。

我记得有一个特定的讲座，在我的教材中也有强调，算法边界（上限、紧密和下限）和情况（最佳、平均和最差）并不相同。但是，我无论如何都想不起这两个概念的区别。

对我来说，如果某个算法在最坏情况下是O(n)，那么它可以执行任何比某些线性函数更糟糕的函数，例如f(n)=cn+k。由于我们在最坏情况下保证了这一点，所以在我看来，它的上限也是线性的。

我知道我错了，我只是想不出为什么。

我是一位情境学习者，如果有人能提供一个有意义的例子，其中最坏情况不是上限，或最佳情况不是下限，或平均情况不是紧密边界，那可能是最快的方法。

感谢您对此的任何澄清！

- IAmYourFaja

Answer 1

考虑快速排序的变种，它检查数组是否已经排序，如果没有，则使用第一个元素作为枢轴进行排序。

如果数组已经排序，那么最佳情况是O(n)。这是最好情况行为的上界，如果不太有趣，但仍然有意义。

在随机输入的平均情况下，时间复杂度为O(n^3/2)和Ω(n)。好吧，我稍微作弊了一点，因为它也是Theta(n log n)，但是这个想法是，界限并不总是紧密的，这种缺乏紧密性可能会在我描述平均情况下的界限时表现出来。

如果数组是反向排序的，那么最坏情况是Theta(n²)，因为子问题非常不平衡（每次，我们选择最大元素作为枢轴，导致子问题大小为0和n-1，而不是约n/2和约n/2）。这是最坏情况的紧界，表明算法确实可能如此糟糕，但不会更差。快速排序也是O(n³)，但不是Theta(n³)，因为快速排序没有导致立方行为的输入族。

- the guy formerly known as d

---

感谢您的回复和出色的例子。 如果我解释得正确，您是在说“情况”取决于算法操作的基础数据模型的配置，并且“界限”的概念是约束算法以特定行为（线性，二次等）给定一个案例（给定底层数据的特定配置或状态）的一种方式。 这是正确的理解吗？ 我现在可能真的“明白了”！ - IAmYourFaja

@Mara 对的。同时，如果我们移除变量并考虑一个列表 L = [1, 2, 3]，那么我们有如下九种类型的语句：min(L) ≤ 2，min(L) = 1，min(L) ≥ 0，avg(L) ≤ 3，avg(L) = 2，avg(L) ≥ 1，max(L) ≤ 4，max(L) = 3，max(L) ≥ 2。 - the guy formerly known as d

一个O界不会限制它的特定行为，它只是表明它的行为不会比那个函数更糟。描述一个情况就像是说，“让我们将算法限制在这个特定的输入上，并尝试限制该程序的运行时间”。（平均情况的命名略有些不妥，因为它不是一个情况，而是所有单个情况的平均值。）请参见我的答案以获取替代描述。 - Nicholas Wilson

Answer 2

Case 指的是正在调查的运行时间类型，而 bound 指的是该运行时间的函数。

说一个算法的最坏情况运行时间是 O(f(n)) 等价于说 f(n) 是该算法最坏情况运行时间的渐进上界。

3种情况（最好情况、平均情况和最坏情况）和 5个渐进界限（上界 (O)，紧上界 (o)，下界 (Ω)，紧下界 (ω) 和紧界 (Θ)）提供了15种用于说明运行时间的不同方法。

如果未指定 Case，则可能会出现混淆或灾难。例如，排序算法的下界可以是 Θ(n) 也可以是 Θ(n lg n)，这取决于我们是在讨论最佳情况还是最坏情况。如果 Θ(n^3) 的最坏情况运行时间使工厂停滞不前，那么 Θ(1) 平均情况运行时间就没有意义。

- antonakos

Answer 3

描述： 以上摘自这里。

举个例子： 假设我们有一个算法，需要将数组中的每个元素与数组中的其他元素进行比较。一个简单的实现可能如下所示：

for my $i (0 .. $#array) {
    for my $j (0 .. $#array) {
        next if $j == $i;
        # Compare $i, $j
    }
}

这是O(N^2)的算法。经过一些测试，我们决定这太慢了，所以我们进行了一点优化。

for my $i (0 .. $#array - 1) {
    for my $j ($i + 1 .. $#array) {
        # Compare $i, $j
    }
}

我们刚刚将运行时间减半了 - 耶！你猜怎么着，大O复杂度仍然是O(N^2)。这是因为N^2 / 2只有一个变量部分。

这一部分来自这里。

- Kang

---

康 - 我很感激你非常全面的回答！不过，如果我正确地理解了这些摘录/例子（我可能不是），那么范围似乎在问题层次上相互关联，而运行时则在算法层面上相互关联。如果是这样的话，我必须尊重地不同意！我可以花5分钟写一个指数阶乘（其中T(n)是(2^n)！）你对比示例的解决方案。确实，我们就不会说，在数组中比较元素的问题具有指数/阶乘上限！那么所有算法的上限都将是无穷大！ - IAmYourFaja

教科书例子的要点是，上限仅表示问题至少这么容易解决——也就是说，如果一个问题是O(n)，那么它必须能够按比例或更快地扩展来解决。现在，如果你找到一种算法，可以用与n成比例的运行时间来解决该问题，那么显然你已经证明了该问题属于O(n)（上限为n），但不属于Theta(n)（严格界限），因为可能存在更快的实现方式。你的指数级阶乘解法已经证明了该比较为O(2^n)，但这并不意味着它不是O(n)。 - thiton

Answer 4

一个简单的求和算法，例如，它的时间复杂度为O(n)，O(n^2)，O(n^3)以及所有更高阶的复杂度，其中O表示最坏情况下的上限。当Theta表示严格的界限时，它也在Theta(n)中，但不在Theta(n^2)或Theta(n^0)中。当Omega是下限时，它在Omega(n)，Omega(n^0)以及所有更低阶的复杂度中。

这与最坏/最好/平均情况不同，对于求和函数，它们都是相等的。最坏/最好情况只是确定输入的乐观程度。

- thiton

---

如果我在这里有误解（由踩票指示），我会感激踩票者能够纠正它或至少指出我错在哪里。非常感谢，我喜欢学习。提前致谢。 - thiton

Answer 5

考虑一个函数，它接受一个包含N+1个整数的列表。如果第一个元素为0，则该函数以随机均匀的方式调用Th(log n)或Th(n)函数来处理数据。同样地，如果第一个元素为1，则调用Th(n^2)来处理数据。对于第一个元素的所有其他值，调用Th(n^1.5)或Th(n log n)函数。我们可以这样描述这个函数的复杂度：

1. 最好情况：Ω(log n)，Omicron(n)
2. 平均情况*：Ω(n log n)，Omicron(n^1.5)

3. 最坏情况：Ω/Omicron/Theta(n^2)

   • 假设第一个元素的可能值足够大。

此外，请注意，复杂度涉及算法的实现；您可以通过添加虚拟循环来增加算法的时间复杂度，而复杂性/可计算性理论研究解决计算问题所需的算法的最小复杂度。微妙的区别。

- Patrick87

Answer 6

谈论一个“情况”意味着您正在考虑算法在某些特定输入上的性能。 “最坏情况”意味着“对于我们即将讨论的内容，请考虑在所有可能的输入上运行所有内容，并将该语句应用于最慢的运行”，等等。

边界是不等式，即某些东西小于或大于其他东西的陈述。复杂度的边界说无论其复杂度函数如何，它都大于或小于指定的事物。大O，小o，Omega都是告诉您有关边界的符号。如果某个东西是O（n），那么这意味着所描述的算法的运行，在满足参数n的输入上，永远不会比某些线性函数更糟糕，渐近地（或者更详细地说，存在一些N和c，对于所有n> N，cn击败了算法的运行时间）。

这并不太糟糕：O、o、Omega，只需告诉你问题的边界。然后你可以谈论最佳情况或最坏情况等方面的边界。例如，大多数排序算法的最佳情况是O(n)。你可以对最坏情况下的边界进行限制，这显然也是所有情况下的边界。Theta是一种特殊的符号：Theta(f)表示O(f)和Omega(f)，这意味着边界是紧密的，不能改进。这是一个确切的陈述。

在某些输入上表现得更好的算法可能没有Theta边界，但当你谈论特定的输入时，总是希望找到一个。通常很容易将关于O边界的陈述加强为关于算法在其最坏情况输入下的Theta陈述。

因此，每个算法都有一个复杂度，你可能会努力去确定或证明它。你想获得尽可能小的上限（压缩O），以及最大的下限。对算法的特定情况进行证明，或者对所有输入进行平均处理，通常也会给你提供有趣和有用的信息。

- Nicholas Wilson