有关时间复杂度的澄清

Question

我需要一些有关算法时间复杂度的帮助。算法的最佳情况和最坏情况时间复杂度究竟是多少？我的理解是，最好的情况时间复杂度是系统终止算法所需执行的最少基本操作数的估计。另一方面，最坏情况的时间复杂度是系统在执行算法时必须执行的基本操作的最大数量。我的理解正确吗？

作为示例，考虑冒泡排序的基本 C++ 代码：

     int count = 0;
     while(count<=n-1)
     {
         bool check = false;
         int index = 0;
         while(index<=n-1)
         {
             if(array[index] > array[index + 1])
             {
                 swap(array[index],array[index + 1]);
                 check = true;
             }
             index++;
         }
         if(check != true)
         {break;}
         else{count++;}
     }

在上面的代码中，当数组按降序排序时，大小为 n 的数组的最坏情况时间复杂度应该是 O(n^2)，这是有意义的，因为系统会生成 (n-1 ) 交换外循环的第一次迭代，(n-2) 交换外循环的第二次迭代，依此类推。因此，算法结束时的操作总数为 (n-1) + (n-2) + .... + 1 = n*(n-1) )/2。忽略常量和低次项，最坏情况的时间复杂度为 O(n^2)。 类似地，算法的最佳情况时间复杂度为 Ω(n)，因为系统必须遍历元素一次，并且在数组已排序的情况下，如果不进行交换，系统就会终止。 我的问题是，当数组的输入大小为零时，最好的情况时间复杂度不应该是 Ω(1) （即当数组为空时）？输入大小为零是否更多是异常/边缘情况，并且输入大小不等于零的任何其他数组的最佳情况时间复杂度将为 Ω(n) ？

此外，最佳和最坏情况时间复杂度的表示法到底是什么？我相信我们对最坏情况有大 - O 表示法，对最好情况有 omega 表示法。然而，我也遇到过使用 big - O 来实现最佳情况时间复杂度的来源。

如果有人可以用示例向我详细解释这个概念，我将不胜感激。不要介意一些小错误（如果有的话），因为这是我第一次使用 Stack Overflow。预先感谢。

Answer 1

我的问题是最好的情况时间复杂度不应该是 Ω(1) 数组的输入大小为零（即当数组为空时）？

不，因为您将时间复杂度确定为输入大小的函数，正如我们所说，“随着

n

变大”。我们想要输入大小为

n

的最佳情况，而不是我们选择

n

的最佳情况。我们确实可以选择输入，但不能选择输入的大小。

另外，最佳和最坏情况时间的表示法到底是什么 复杂性？我相信我们有最坏情况的大 - O 表示法 欧米茄最好的情况。然而，我遇到过使用的来源 big - O 也代表最佳情况时间复杂度。

这是一个常见的误解。 Big-O 意味着 最坏情况，Big-Omega 意味着 最好情况，Big-Theta 意味着 平均情况，这是不正确的。

Big-O 是一个上限。我们通常对最坏情况的上限感兴趣，因此 Big-O 与最坏情况行为相关联，但我们也可能对平均情况行为的上限感兴趣，等等。

我们对最坏情况下的上限感兴趣，因为当我们使用应用于运行时间的渐近符号时，“更高”的函数更糟糕，因此上限在某种意义上是好的。如果算法有一个上限，比如 O(n^3) 时间，这比有一个下限 Ω(n^3) 更好，因为下限意味着它可能会更糟，可能会更慢，不优于下限。