时间戳

首页 > 解决方案 > 单for循环冒泡排序的时间复杂度

data-structures - 单for循环冒泡排序的时间复杂度

问题描述

我研究了冒泡排序是一种 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 循环，当它等于 N 时设置计数器 i。根据我的说法，循环是 O(n)，它会重置 n-1 次。因此，它变为 O(n) + O(n-1) = O(n)。我对么？如果不是这个代码的复杂性应该是什么。

标签： data-structuresbubble-sort

解决方案

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

您的循环在i == N. 你是对的 - 循环得到重新初始化的(n-1)时间。现在每个时间循环都执行时间的 then 值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

推荐阅读