algorithm - 算法的最坏情况和平均情况运行时间之间的关系

Question

假设 A(n) 是算法的平均运行时间，而 W(n) 是最差的。这样说是否正确

A(n) = O(W(n))

总是正确的？

Answer 1

Big O 表示法有点棘手，因为它只定义了给定算法执行时间的上限。

这意味着，如果f(x) = O(g(x))对于每个其他功能h(x)，g(x) < h(x)您将拥有f(x) = O(h(x)). 问题是，那些超出预期的执行时间有用吗？明确的答案根本不是。您通常想要的是您可以获得的“最小”上限，但这在定义中并不是严格要求的，因此您可以使用它。

您可以使用其他符号（例如 Big Theta）获得更严格的界限，您可以在此处阅读。

因此，您的问题的答案是肯定的A(n) = O(W(n))，但这并没有提供有关算法的任何有用信息。

Answer 2

如果你提到 A(n) 和 W(n) 是函数——那么，是的，你可以在普通情况下做这样的陈述——这是因为 big-o正式定义。

请注意，就big-o而言，这样做是没有意义的——因为它会使对真正复杂性的理解变得更糟。（一般来说，三种情况——最差、平均、最好——准确地呈现出复杂性更清楚）

Answer 3

是的，这样说并没有错。

人们使用渐近符号来根据输入大小来传达特定情况下运行时间的增长。将平均情况复杂性与最坏情况复杂性进行比较并不能深入了解函数在任何一种情况下的增长。
虽然它没有错，但它未能提供比我们已经知道的更多的信息。

Answer 4

我不确定您到底想问什么，但请记住以下内容。

用于显示平均和最坏情况运行时间复杂度之间差异的典型算法是快速排序，其中枢轴选择不当。

平均而言，对于未排序数据的随机样本，运行时复杂度为n log(n). 但是，对于已经排序的数据集，其中枢轴来自列表的前端/末端，运行时复杂度为n^2.