如何计算冒泡排序时间复杂度 [英] how to calculate Bubble sort Time Complexity

问题描述

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

I was trying to understand the Data Structure and different algorithm, then i got confused to measure the Bubble sort time complexity.

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等。这意味着在每次迭代中其值都会下降。
例如，如果我有a [] = {4、2、9、5、3、6、11}，则比较的总数为-

Now every Big O tells Best case O(n), Avg case(n2) and Worst Case(n2).But when i see the code, found in first phase inner loop run n time then in second phase n - 1, and n - 2 and so on. That means in every iteration its value goes down. For example if i have a[] = {4, 2, 9, 5, 3, 6, 11} so the total number of comparison will be -

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

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

so when i calculate the time it looks like = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35, but the worst time complexity is n2 as per doc.

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

so can Someone tell me how to calculate the correct value.

推荐答案

让我们看一下Big O进行Bubble Sort的案例

Let's go through the cases for Big O for Bubble Sort

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

Case 1) O(n) (Best case) This time complexity can occur if the array is already sorted, and that means that no swap occurred and only 1 iteration of n elements

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

Case 2) O(n^2) (Worst case) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs. Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

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

In your example, it may not examine these many elements in each phase as the array is not in descending order.

这篇关于如何计算冒泡排序时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！