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

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;
    }
  }
}

现在每一个大O都表示最佳情况O(n)、Avg情况(n2)和最坏情况(n2)，但当我看到代码时，发现在第一阶段内循环运行了n次，然后在第二阶段内循环运行了n-1和n-2等等。这意味着在每次迭代中，它的值都会下降。例如，如果我有一个[]={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

Answer 1

让我们来看看泡泡排序的大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)

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