使用 Big-O 表示法时平均复杂度的含义
在回答这个问题时，关于快速排序复杂性的争论开始了。我大学时记得的是，QuickSort 在最坏情况下为 O(n^2)，在平均情况下为 O(n log(n))，而 最好情况下为 O(n log(n)) （但有更严格的限制）。
我需要的是对平均复杂度含义的正确数学解释，以便向那些相信大 O 表示法只能用于最坏情况的人清楚地解释它的含义。
我记得如果要定义平均复杂度，您应该考虑所有可能输入的算法复杂度，计算有多少退化和正常情况。如果当 n 变大时，退化情况的数量除以 n 趋向于 0，那么您可以说正常情况下整个函数的平均复杂度。
这个定义正确还是平均复杂度的定义不同？如果它是正确的，有人能比我更严格地表述吗？
While answering to this question a debate began in comments about complexity of QuickSort. What I remember from my university time is that QuickSort is O(n^2) in worst case, O(n log(n)) in average case and O(n log(n)) (but with tighter bound) in best case.
What I need is a correct mathematical explanation of the meaning of average complexity to explain clearly what it is about to someone who believe the big-O notation can only be used for worst-case.
What I remember if that to define average complexity you should consider complexity of algorithm for all possible inputs, count how many degenerating and normal cases. If the number of degenerating cases divided by n tend towards 0 when n get big, then you can speak of average complexity of the overall function for normal cases.
Is this definition right or is definition of average complexity different ? And if it's correct can someone state it more rigorously than I ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
你说得对。
大 O（大 Theta 等）用于测量函数。当你写 f=O(g) 时，f 和 g 的含义并不重要。它们可以是平均时间复杂度、最差时间复杂度、空间复杂度、表示素数分布等。
最坏情况复杂度是一个大小为 n 的函数，它告诉您一个问题的最大步数是多少给定大小为 n 的输入的算法。
平均情况复杂度是一个采用大小为 n 的函数，它告诉您给定大小为 n 的输入的算法的预期步骤数。
正如您所看到的，最坏情况和平均情况的复杂性都是函数，因此您可以使用大 O 来表达它们的增长。
You're right.
Big O (big Theta etc.) is used to measure functions. When you write f=O(g) it doesn't matter what f and g mean. They could be average time complexity, worst time complexity, space complexities, denote distribution of primes etc.
Worst-case complexity is a function that takes size n, and tells you what is maximum number of steps of an algorithm given input of size n.
Average-case complexity is a function that takes size n, and tells you what is expected number of steps of an algorithm given input of size n.
As you see worst-case and average-case complexity are functions, so you can use big O to express their growth.
如果您正在寻找正式的定义，那么：
平均复杂度是预期运行时间随机输入。
If you're looking for a formal definition, then:
Average complexity is the expected running time for a random input.
我们参考一下维基百科中的Big O Notation：
那么定义的前提是函数 f 应该接受一个数字作为输入并产生一个数字作为输出。我们所说的输入数字是什么？据说它是要排序的序列中的许多元素。我们可以谈论什么输出数字？它可能是为了对序列进行排序而完成的许多操作。但停下来。什么是函数？ 维基百科中的函数：
我们是否按照之前的定义生成恰好一个输出？不，我们不。对于给定大小的序列，我们可以获得各种不同的操作数。因此，为了确保定义适用于我们的情况，我们需要将一组可能的结果（操作数量）减少到单个值。它可以是最大值（“最坏情况”）、最小值（“最好情况”）或平均值。
结论是，谈论最佳/最差/平均情况在数学上是正确的，并且在没有排序复杂性的情况下使用大 O 表示法有点草率。
另一方面，我们可以更精确，使用大 Theta 表示法而不是大 O 表示法。
Let's refer Big O Notation in Wikipedia:
So what the premise of the definition states is that the function f should take a number as an input and yield a number as an output. What input number are we talking about? It's supposedly a number of elements in the sequence to be sorted. What output number could we be talking about? It could be a number of operations done to order the sequence. But stop. What is a function? Function in Wikipedia:
Are we producing exacly one output with our prior defition? No, we don't. For a given size of a sequence we can get a wide variation of number of operations. So to ensure the definition is applicable to our case we need to reduce a set possible outcomes (number of operations) to a single value. It can be a maximum ("the worse case"), a minimum ("the best case") or an average.
The conclusion is that talking about best/worst/average case is mathematically correct and using big O notation without those in context of sorting complexity is somewhat sloppy.
On the other hand, we could be more precise and use big Theta notation instead of big O notation.
我认为你的定义是正确的，但你的结论是错误的。
如果“坏”情况的比例趋向于 0，则平均复杂度不一定等于“正常”情况的复杂度。
例如，假设 1/(n^2) 种情况是“坏”情况，其余情况是“正常”情况，并且“坏”情况正好需要 (n^4) 次操作，而“正常”情况正好需要 n 次操作。
那么平均所需的操作次数等于：
这个函数是 O(n^2)，但不是 O(n)。
但在实践中，您可能会发现在所有情况下时间都是多项式的，并且“坏”情况的比例呈指数下降。那时你会在计算平均值时忽略坏情况。
I think your definition is correct, but your conclusions are wrong.
It's not necessarily true that if the proportion of "bad" cases tends to 0, then the average complexity is equal to the complexity of the "normal" cases.
For example, suppose that 1/(n^2) cases are "bad" and the rest "normal", and that "bad" cases take exactly (n^4) operations, whereas "normal" cases take exactly n operations.
Then the average number of operations required is equal to:
This function is O(n^2), but not O(n).
In practice, though, you might find that time is polynomial in all cases, and the proportion of "bad" cases shrinks exponentially. That's when you'd ignore the bad cases in calculating an average.
平均案例分析执行以下操作：
获取固定长度（例如
n）的所有输入，总结该长度的所有实例的所有运行时间，并计算平均值。问题是您可能必须枚举长度为 n 的所有输入才能得出平均复杂度。
Average case analysis does the following:
Take all inputs of a fixed length (say
n), sum up all the running times of all instances of this length, and build the average.The problem is you will probably have to enumerate all inputs of length
nin order to come up with an average complexity.