kri*_*iss 11 algorithm complexity-theory big-o
在回答这个问题时,一场辩论开始于对QuickSort复杂性的评论.我在大学时代记得的是,在最好的情况O(n^2)下,QuickSort是最坏的情况,O(n log(n))在平均情况下O(n log(n))(但是受到更严格的约束).
我需要的是一个正确的数学解释,意思是average complexity清楚地解释一下那些相信大O符号只能用于最坏情况的人.
我记得如果要定义平均复杂度,你应该考虑所有可能输入的算法的复杂性,计算有多少退化和正常情况.如果当n变大时,退化情况除以n的数量倾向于0,则可以说正常情况下整体函数的平均复杂度.
这个定义是正确的还是平均复杂度的定义不同？如果它是正确的,有人可以比我更严格地陈述它吗？
sdc*_*vvc 10
你是对的.
Big O(大Theta等)用于测量功能.当你写f = O(g)时f和g意味着什么并不重要.它们可能是平均时间复杂度,最差时间复杂度,空间复杂性,表示素数的分布等.
最坏情况复杂度是一个取n大小的函数,并告诉你在给定大小为n的情况下算法的最大步数是多少.
平均大小写复杂度是一个取n大小的函数,并告诉您在给定大小为n的情况下算法的预期步数.
如您所见,最坏情况和平均情况复杂性是函数,因此您可以使用大O来表示它们的增长.