在回答这个问题时，围绕QuickSort复杂性的评论开始了辩论。我上大学时记得的是，QuickSort
O(n^2)在最坏的情况下，O(nlog(n))在一般情况下，O(nlog(n))但（在更严格的范围内）在最好的情况下。

我需要的是对的含义的正确数学解释，average complexity以便向相信big-O表示法只能在最坏的情况下使用的人清楚地解释它的含义。

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

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