0

我做了下面的代码来检查冒泡排序和插入排序所需的迭代次数和交换次数。即使（参考下面的代码）与冒泡排序相比，插入排序实际上做了一半的迭代和相同数量的交换，但是为什么两者都具有相同的 BIG-O 复杂度

static void bubbleSortExample()
    {
        int iterationCount=0;
        int swaps=0;
        int [] arr={2,6,1,4,8,7,10,3};
        int temp=0;
        for(int i=0; i< arr.length; i++)
        {
            iterationCount=iterationCount+1;
            for(int j=0; j<arr.length-1; j++)
            {
                iterationCount=iterationCount+1;
                if(arr[j]> arr[j+1])
                {
                    swaps= swaps+1;
                    temp= arr[j+1];
                    arr[j+1]= arr[j];
                    arr[j]= temp;
                }
            }
        }
        System.out.println("Bubble Sort----Iteration count are : " + iterationCount + " and swaps are : " + swaps);
    }
    //Bubble Sort Example Ends


    //Insertion Sort Example Starts
    static void insertionSortExample()
    {
        int iterationCount=0;
        int swaps=0;
        int [] arr={2,6,1,4,8,7,10,3};

        for(int i=1;i< arr.length;i++)
        {
            iterationCount=iterationCount+1;
            int key=arr[i];// this is the number that needs to be inserted in its correct position
            for(int j=i-1; j >= 0;  j--)
            {
                iterationCount=iterationCount+1;
                if(key < arr[j])
                {
                    swaps= swaps+1;
                    int t= arr[j];
                    arr[j]=key;
                    arr[j+1]=t;

                }
            }
        }
        System.out.println("Insertion Sort----Iteration count are : " + iterationCount + " and swaps are : " + swaps);
    }

输出

Bubble Sort----Iteration count are : 64 and swaps are : 9
Insertion Sort----Iteration count are : 35 and swaps are : 9
4

3 回答 3

3

哇！哇！等等。你混淆了两件事。
一个是运行时间，它是程序在输入实例上的实际运行时间。
其次是时间复杂度，即运行时间如何随着输入大小的增长而增长。

在实践中，O(N^2) 的程序可以比 O(NlogN) 的代码运行得快得多。这是因为输入可能主要是平均情况，但是 Big-Oh 分析仅用于最坏情况分析.这是因为 Big-Oh 没有告诉实际运行时间（这可能取决于输入的性质（最佳情况/最坏情况），实际实现的细节）。Big-Oh 只给我们一个算法不会运行的保证比该函数的常数倍差。

你可以在这里阅读我的答案来澄清这些。

因此，当我们说冒泡排序/插入排序是 O(N 2 ) 时，我们的意思是说最坏情况下的运行时间不大于常数倍 N^2。意识到这确实是两种算法。

如果您仍然有困惑，请随时询问。

于 2013-07-09T10:39:09.787 回答
1

请记住，该符号仅表示算法在 n 增长时的行为方式。一个线性因子总是从中删除。所以它实际上并没有说明算法是否很快，它只是说明了随着 n 的增加需要更多时间来完成的因素。

于 2013-07-09T11:32:23.420 回答
0

在第 i 次迭代中的冒泡排序中，您总共有 ni-1 次内部迭代 (n^2)/2，但在插入排序中，您在第 i 步有最大 i 次迭代，但平均为 i/2，因为您可以停止内部循环早些时候，在您找到当前元素的正确位置之后。

所以你有 (sum from 0 to n) / 2 是 (n^2) / 4 总数；

这就是插入排序比冒泡排序快的原因。

于 2013-07-09T10:09:00.087 回答