algorithm - 如何计算冒泡排序时间复杂度

Question

我试图了解数据结构和不同的算法，然后我对测量冒泡排序的时间复杂度感到困惑。

for (c = 0; c < ( n - 1 ); c++) {
  for (d = 0; d < n - c - 1; d++) {
    if (array[d] > array[d+1]) /* For descending order use < */
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

现在每个 Big O 都告诉 Best case O(n)，Avg case(n2) 和 Worst Case(n2)。但是当我看到代码时，发现在第一阶段内部循环运行 n 次然后在第二阶段 n - 1 , 和 n - 2 等等。这意味着在每次迭代中它的值都会下降。 例如，如果我有 a[] = {4, 2, 9, 5, 3, 6, 11} 那么比较的总数将是 -

1st Phase - 7 time
2nd phase - 6 time
3rd Phase - 5 time
4th Phase - 4 time
5th Phase - 3 time
6th Phase - 2 time
7th Phase - 1 time

所以当我计算时间时，它看起来像 = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35，但根据文档，最差的时间复杂度是 n2。

有人可以告诉我如何计算正确的值吗？

Answer 1

让我们通过冒泡排序的 Big O 案例

情况 1) O(n)(最佳情况) 如果数组已经排序，就会出现这种时间复杂度，这意味着没有发生交换，只有 n 个元素的 1 次迭代

情况 2) O(n^2)(最坏情况) 最坏的情况是数组已经排序但按降序排列。这意味着在第一次迭代中它必须查看 n 个元素，然后它会查看 n - 1 个元素(因为最大的整数在末尾)等等，直到发生 1 次比较。 Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

在您的示例中，它可能不会在每个阶段检查这么多元素，因为数组不是按降序排列的。