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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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），平均情况（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

因此，当我计算时间时，它看起来像是=（7 + 6 + 5 + 4 + 3 + 2 + 1）+ 7 = 35，但最差的时间复杂度是每个文档n2。

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

回答：

让我们看一下大O进行冒泡排序的案例

情况1）O（n）（最佳情况）如果已经对数组进行了排序，则可能会发生这种时间复杂性，这意味着没有交换发生，只有n个元素的1次迭代

情况2）O（n ^

2）（最坏的情况）最坏的情况是如果数组已经排序但以降序排列。这意味着在第一次迭代中，它必须先看n个元素，然后再看n-1个元素（因为最大的整数在末尾），依此类推，直到发生1个比较。大O

= n + n-1 + n-2 … + 1 =（n *（n + 1））/ 2 = O（n ^ 2）

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

以上是 如何计算冒泡排序时间复杂度 的全部内容， 来源链接： utcz.com/qa/431129.html

回到顶部