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

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等等.这意味着在每次迭代中它的值都会下降.例如,如果我有[] = {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的时间时,但是最差的时间复杂度是按照doc的n2.

有人告诉我如何计算正确的值.

Answer 1

让我们来看看Big O for Bubble Sort的案例

情况1)O(n)(最佳情况)如果数组已经排序,则可能发生这种时间复杂性,这意味着没有发生交换,只有1次迭代的n个元素

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

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

Answer 2

所以你已经注意到完成的比较总数是n +(n - 1)+ ... + 2 + 1.这个和等于n*(n + 1)/ 2(见三角数),这是等于0.5 n ^ 2 + 0.5 n,显然是O(n ^ 2).