时间戳

首页 > 解决方案 > 具有相同迭代的两种不同冒泡排序方法的时间复杂度

java - 具有相同迭代的两种不同冒泡排序方法的时间复杂度

问题描述

我正在实现一个冒泡排序算法，我很困惑下面给出的两个 java 方法是否会给出相同的时间复杂度或者会不同：

void bubbleSort(int arr[]) 
    { 
        int n = arr.length;             
        for (int i = 0; i < n-1; i++)               
        {
            for (int j = 0; j < n-i-1; j++)         
                
            {
                if (arr[j] > arr[j+1]) 
                { 
                    // swap arr[j+1] and arr[j] 
                    int temp = arr[j]; 
                    arr[j] = arr[j+1]; 
                    arr[j+1] = temp; 
                } 
            }
        }
    }

这种方法有 O(N^2) 时间复杂度——我很确定。

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

我不确定这个，因为它使用单循环进行相同的迭代？

标签： javadata-structures

解决方案

两种实现具有相同的复杂性，通过比较它们的迭代次数很容易看出。让我们在发生迭代的地方添加计数器，并在排序后比较它们的值：

    class Main  {
    private static int count1 = 0, count2 = 0;
    public static void main(String[] args) {
        int[] array1 = new int[]{1, 6, -4, 0, 12, -8}, array2 = new int[]{1, 6, -4, 0, 12, -8};;
        bubbleSort1(array1);
        bubbleSort2(array2);
        System.out.println(count1);
        System.out.println(count2);
    }

    private static void bubbleSort1(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; ++i) {
            ++count1;
            for (int j = 0; j < n-i-1; ++j) {
                ++count1;
                if (arr[j] > arr[j+1]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    private static void bubbleSort2(int arr[]) {
        int n = arr.length;
        int i = 0, j = 0;
        while (i < n - 1) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
            ++j;
            ++count2;

            if (j == n - i - 1) {
                j = 0;
                ++i;
                ++count2;
            }
        }
    }
}

输出：

20
20

在复杂性评估中，重要的不是周期数，而是算法本身，这里也是 O(n^2)。

推荐阅读