algorithm - 使用 Big-O 表示法时平均复杂度的含义

Question

在回答 this question 时一场关于 QuickSort 复杂性的讨论开始了。我记得我大学时的情况是，QuickSort 在最坏情况下是 O(n^2)，在一般情况下是 O(n log(n)) 而 O(n log(n))(但有更严格的限制)在最好的情况下。

我需要的是对 average complexity 含义的正确数学解释，以便向那些认为大 O 表示法只能用于最坏情况的人清楚地解释它的含义。

我记得如果要定义平均复杂度，您应该考虑所有可能输入的算法复杂度，计算退化和正常情况的数量。如果当 n 变大时，退化案例的数量除以 n 趋于 0，那么您可以说是正常案例的整体功能的平均复杂度。

这个定义是正确的还是平均复杂度的定义不同？如果它是正确的，有人能比我更严格地陈述它吗？

Answer 1

你是对的。

Big O(大 Theta 等)用于测量功能。当您编写 f=O(g) 时，f 和 g 的含义无关紧要。它们可以是平均时间复杂度、最坏时间复杂度、空间复杂度、表示素数分布等。

最坏情况复杂度 是一个大小为 n 的函数，它告诉您给定大小为 n 的输入的算法的最大步数是多少。

平均情况复杂度 是一个大小为 n 的函数，它告诉您给定大小为 n 的输入的算法的预期步数。

如您所见，最坏情况和平均情况的复杂度是函数，因此您可以使用大 O 来表达它们的增长。