平均复杂度的使用大O符号时含义 [英] Meaning of average complexity when using Big-O notation

问题描述

在回答到这个问题辩论始于约的复杂性意见快速排序。我记得我上大学的时间是快速排序是为O（n ^ 2）在最坏的情况下， O（N日志（N））的平均情况和 O（N日志（N））（但有更严格的约束），在最好的情况下。

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.

我需要的是的平均复杂解释清楚的意思正确的数学解释它是什么的人谁相信大O记法只能用于为最坏的情况。

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.

我记得如果是定义平均的复杂性，你应该考虑算法的复杂性，为所有可能的输入，计算有多少退化和正常的情况下。如果退化的情况下，除以n个数对0倾向于当n变大，那么你能说出的平均总体功能正常的情况下的复杂性。

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 ?

推荐答案

如果你正在寻找一个正式的定义，那么：

If you're looking for a formal definition, then:

平均复杂度是预计的运行时间进行随机输入。

Average complexity is the expected running time for a random input.

这篇关于平均复杂度的使用大O符号时含义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！