假设 A(n) 是算法的平均运行时间，W(n) 是最差的。这样说是否正确
A(n) = O(W(n))
总是正确的吗？
最佳答案
Big O 表示法有点棘手，因为它只定义给定算法执行时间的上限。
这意味着，如果 f(x) = O(g(x))然后对于每个其他函数 h(x)这样g(x) < h(x)你将会有f(x) = O(h(x)) 。问题是，那些超过预期的执行时间有用吗？明确的答案是根本不是。你通常想要的是“最小”
你可以得到上限，但这在定义中并不是严格要求的，所以你可以尝试一下。
您可以使用其他符号(例如 Big Theta)获得更严格的界限，如您可以阅读 here .
所以，你的问题的答案是肯定的，A(n) = O(W(n)) ，但这并没有提供有关算法的任何有用信息。
关于algorithm - 算法的最坏情况和平均情况运行时间之间的关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18330654/