单循环冒泡排序的时间复杂度

Question

我研究过冒泡排序是一个复杂度O(n^2)的算法。但是我设计了一个看起来像 O(n) 的算法。以下是我的代码：

void bubbleSort(int[] arr) {
int counter = 1, i = 0;
int N = arr.length-counter;
for(i=0; i<N; ){
  if(arr[i]>arr[i+1]){
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
  }
  i++;
  if(i == N){
    N = arr.length - (++counter);
    i = 0;
  }
}

有一个for循环，当计数器i等于N时设置计数器i。根据我的说法，循环是O(n)，它会重置n-1次。所以，它变成了 O(n) + O(n-1) = O(n)。我对么？如果不是，这段代码的复杂度应该是多少。

Answer 1

不，你错了。有一个循环并不意味着它是 O(n)。您必须考虑执行了多少步骤。

您的循环在 i == N 时重新初始化。你是对的 - 循环被重新初始化 (n-1) 次。现在每次循环执行 N 次的 then 值。所以它不是 O(n) + O(n-1) 而是 O(n*(n-1)) 最终导致 O(n^2).

例如 -

at first pass, loop will be executed (N) times. then N will be re-initialized to (N-1)
at second pass, loop will be executed (N-1) times. then N will be re-initialized to (N-2)
...
...
this will go on in total of (n-1) times.

所以会是-O(N + (N - 1) + (N - 2) + ... + 1)，会被计算成O(n^2)

出于实验目的，您可以全局初始化一个计数器。并检查程序执行的总步骤的值是多少，以检查实际发生了什么 -

void bubbleSort(int[] arr) {
int counter = 1, i = 0;
int total = 0;
int N = arr.length-counter;
for(i=0; i<N; ){
  total++;
  if(arr[i]>arr[i+1]){
    int temp = arr[i];
    arr[i] = arr[i+1];
    arr[i+1] = temp;
  }
  i++;
  if(i == N){
    N = arr.length - (++counter);
    i = 0;
  }
}
printf(%d", total); // this will give you total number of steps executed. check for various value of n

Answer 2

你的循环在你的外循环中初始化 n-1 次所以

循环将按以下方式执行

对于外循环的每次迭代，内循环 n-1 次，即外循环的 n 次迭代 * 内循环的 n-1 次迭代 = (n*n-1) = n2 使其复杂度为 O(n2)

Answer 3

答案就在你自己的陈述中：

There is one for loop and the counter i is set when it is equal to N. According to me the loop is O(n) and it resets for n-1 times. So, it becomes O(n) + O(n-1) = O(n). Am I correct? If not what should be the complexity of this code.

只有一个循环。正确。
该循环的时间复杂度为 O(n)。正确。
循环重置n-1次。正确。
但是计算错误

如果循环重置n-1次，复杂度变为： O(n)+O(n-1)+O(n-2)+....+O(1) 本质上是 O(n^2).

单循环冒泡排序的时间复杂度

Time complexity of bubble sort with single for loop

bubble-sort

data-structures