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

Question

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

Answer 1

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

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

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

我们以快速排序为例。

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

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

Answer 2

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