带有单个for循环的冒泡排序的时间复杂度

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次的值。因此，最终导致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

答案在于您自己的陈述：

存在一个for循环，当计数器i等于N时，将设置计数器i。根据我的说法，该循环为O（n），它会重置n-1次。因此，它变为O（n）+ O（n-1）= O（n）。我对么？如果不是，那么此代码的复杂性应该是什么。

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

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