在回答this question时，一场关于QuickSort复杂性的评论开始了争论。我在大学时间记得的是，在最糟糕的情况下，QuickSort是O(n^2)，在平均情况下是O(n log(n))，在最好的情况下是O(n log(n))（但是有更严格的约束）。
我需要的是对average complexity含义的正确数学解释，以清楚地解释那些认为大O符号只能用于最坏情况的人的意思。
我记得如果要定义平均复杂度，你应该考虑所有可能输入的算法的复杂性，计算有多少退化和正常情况。如果当n变大时，退化情况除以n的数量倾向于0，则可以说正常情况下整体函数的平均复杂度。
这个定义是正确的还是平均复杂度的定义不同？如果它是正确的，有人可以比我更严格地陈述它吗？
如果您正在寻找正式的定义，那么：
平均复杂度是随机输入的expected运行时间。
你是对的。
Big O（大Theta等）用于测量功能。当你写f = O（g）时f和g意味着什么并不重要。它们可能是平均时间复杂度，最差时间复杂度，空间复杂性，表示素数的分布等。
最坏情况复杂度是一个取n大小的函数，并告诉你在给定大小为n的情况下算法的最大步数是多少。
平均大小写复杂度是一个取n大小的函数，并告诉您在给定大小为n的情况下算法的预期步数。
如您所见，最坏情况和平均情况复杂性是函数，因此您可以使用大O来表示它们的增长。
我认为你的定义是正确的，但你的结论是错误的。
如果“坏”案例的比例趋于0，那么平均复杂性等于“正常”案例的复杂性并不一定如此。
例如，假设1 /（n ^ 2）个案例为“坏”而其余为“正常”，而“坏”案例则采用精确（n ^ 4）个操作，而“正常”个案恰好执行n个操作。
然后所需的平均操作数等于：
(n^4/n^2) + n(n^2-1)/(n^2)
该函数是O（n ^ 2），但不是O（n）。
但实际上，在所有情况下，您可能会发现时间是多项式的，而“坏”案例的比例会呈指数级缩小。那是你在计算平均值时忽略不良情况的时候。
平均案例分析执行以下操作：
获取固定长度的所有输入（比如n），总结此长度的所有实例的所有运行时间，并构建平均值。
问题是你可能需要枚举长度为n的所有输入，以便得出平均复杂度。
我们来推荐Big O Notation in Wikipedia：
设f和g是在实数的某个子集上定义的两个函数。一个人写
f(x)=O(g(x)) as x --> infinity如果......
那么定义陈述的前提是函数f应该将一个数作为输入并产生一个数作为输出。我们在谈论什么输入数字？据推测，序列中有许多元素需要排序。我们可以谈论什么输出数字？它可以是为了对序列进行排序而进行的许多操作。但是停下来。什么是功能？ Function in Wikipedia：
函数是一组输入和一组允许输出之间的关系，其属性是每个输入与一个输出完全相关。
我们之前的定义是否真的产生了一个输出？不，我们没有。对于给定大小的序列，我们可以获得大量的操作变化。因此，为了确保定义适用于我们的案例，我们需要将一组可能的结果（操作数）减少到单个值。它可以是最大值（“最坏情况”），最小值（“最佳情况”）或平均值。
结论是，谈论最佳/最差/平均情况在数学上是正确的，并且在没有排序复杂性的情况下使用大O表示法有点草率。
另一方面，我们可以更精确并使用大的Theta符号而不是大O符号。