算法的最坏情况时间复杂度与其上限之间的关系/差异是什么?
2 回答
术语“上限”不是很清楚,因为它可能指的是两种可能的东西:
算法的上限 - 算法永远不会比它“慢”运行的界限。这基本上是它最坏的情况下的表现,所以如果这就是你的意思 - 答案很简单。
big-O 表示法,它提供了特定分析下算法复杂度的上限。big-O 表示法是一组函数,可以应用于算法的任何分析,包括最坏情况、平均情况,甚至最佳情况。
我们以快速排序为例。
据说快速排序具有O(n^2)
最差情况下的性能和O(nlogn)
平均情况下的性能。一种算法怎么可能有两种复杂性?很简单,代表平均情况分析的函数和代表最坏情况的函数是完全不同的函数——我们可以对它们中的每一个应用大 O 表示法,没有任何限制。
此外,我们甚至可以将其应用于最佳情况。考虑一个快速排序的小优化,它首先检查数组是否已经排序,如果是 - 它立即停止。这是有效的O(n)
操作,并且有一些输入会提供这种行为 - 所以我们现在可以说算法的最佳情况复杂度是O(n)
最坏情况和大 O(UPPER BOUND) 之间的区别在于, 最坏情况是您的代码实际发生的情况, 上限是一个高估,我们为了计算大 O 而提出的假设,它没有不必发生
插入排序示例:
最坏的情况下:
这些数字都是反向排列的,所以你需要排列和移动每个数字
伪代码
for j=2 to n
do key = a[i]
i=j-1
while i>0 & a[i]>key
do a[i+1] = a[i]
i=i-1
end while
a[i+1]=key
end for
上限:
我们假设每次内循环的顺序是i =n-1,但实际上每次都是可变的,不可能每次都是n-1,而是我们假设/高估了它来计算大○