1

算法的最坏情况时间复杂度与其上限之间的关系/差异是什么?

4

2 回答 2

3

术语“上限”不是很清楚,因为它可能指的是两种可能的东西:

  1. 算法的上限 - 算法永远不会比它“慢”运行的界限。这基本上是它最坏的情况下的表现,所以如果这就是你的意思 - 答案很简单。

  2. big-O 表示法,它提供了特定分析下算法复杂度的上限。big-O 表示法是一函数,可以应用于算法的任何分析,包括最坏情况、平均情况,甚至最佳情况。

我们以快速排序为例。

据说快速排序具有O(n^2)最差情况下的性能和O(nlogn)平均情况下的性能。一种算法怎么可能有两种复杂性?很简单,代表平均情况分析的函数和代表最坏情况的函数是完全不同的函数——我们可以对它们中的每一个应用大 O 表示法,没有任何限制。

此外,我们甚至可以将其应用于最佳情况。考虑一个快速排序的小优化,它首先检查数组是否已经排序,如果是 - 它立即停止。这是有效的O(n)操作,并且有一些输入会提供这种行为 - 所以我们现在可以说算法的最佳情况复杂度是O(n)

于 2015-04-28T08:43:35.863 回答
0

最坏情况和大 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,而是我们假设/高估了它来计算大○

于 2018-09-25T15:22:06.133 回答