为什么会冒泡排序和插入排序相同，即O（N ^ 2）的性能 [英] Why is performance of bubble sort and insertion sort same i.e O(n^2)

问题描述

我没了下文code检查迭代和所需的冒泡排序和插入排序交换的数量。尽管（指低于code）插入排序做了字面上的一半迭代和掉期相同数量相比，冒泡排序，然后怎么来的都具有同样的BIG-O的复杂性。

 静态无效bubbleSortExample（）
    {
        INT iterationCount = 0;
        INT互换= 0;
        INT [] ARR = {2,6,1,4,8,7,10,3};
        INT TEMP = 0;
        的for（int i = 0; I＆LT; arr.length;我++）
        {
            iterationCount = iterationCount + 1;
            对于（INT J = 0; J＆LT; arr.length-1，J ++）
            {
                iterationCount = iterationCount + 1;
                如果（ARR [J] GT;常用3 [J + 1]）
                {
                    互换=掉期+ 1;
                    TEMP = ARR [J + 1];
                    ARR [J + 1] = ARR [J]。
                    ARR [J] =温度;
                }
            }
        }
        的System.out.println（冒泡排序----迭代次数分别是：+ iterationCount +和掉期分别是：+掉期）;
    }
    //冒泡排序示例完


    //插入排序示例启动
    静态无效insertionSortExample（）
    {
        INT iterationCount = 0;
        INT互换= 0;
        INT [] ARR = {2,6,1,4,8,7,10,3};

        的for（int i = 1; I＆LT; arr.length;我++）
        {
            iterationCount = iterationCount + 1;
            INT键=改编[我]; //这是一个需要正确的位置插入数
            对于（INT J = I-1; J＆GT; = 0; j--）
            {
                iterationCount = iterationCount + 1;
                如果（钥匙＆LT;常用3 [J]。）
                {
                    互换=掉期+ 1;
                    INT T = ARR [J]。
                    ARR [J] =键;
                    ARR [J + 1] = T;

                }
            }
        }
        的System.out.println（插入排序----迭代次数分别是：+ iterationCount +和掉期分别是：+掉期）;
    }
 

OUTPUT

 冒泡排序----迭代次数分别是：64和掉期分别是：9
插入排序----迭代次数分别是：35和掉期分别是：9
 

解决方案

哇！哇！ Wait.You混淆了两件事。
一个是运行时间这是对输入的一个实例程序的实际运行时间。照片 二是时间复杂度这是怎么运行时间的增长作为输入规模的增长。

一个方案，这是O（N ^ 2）可运行超过code这是O（NlogN）的practise.This是因为输入可能主要是平均的情况下要快得多，但是大哦分析只为最坏的情况下analysis.This意思是因为大哦不讲述实际运行时间（其可能依赖于输入（最好的情况下/最坏的情况下），实际的实现细节的性质）。大哦只给我们一个机制保障的一个算法运行速度比恒定的时间不差的函数。

您可以阅读我的​​答案<一href="http://stackoverflow.com/questions/17457999/contradiction-in-cormen-regarding-insertion-sort/17462849#17462849">here澄清这些。

所以，当我们说冒泡排序/插入排序是O（N ² ），我们的意思是说，在最坏的情况下的运行时间不超过一个恒定的次数N ^ 2大.Realize，这的确对于两种算法的情况下。

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

I did the below code to check the number of iteration and swaps required for bubble sort and insertion sort. Even though (referring to below code) insertion sort did literally half iterations and same number of swaps as compared to bubble sort then how come both have same BIG-O complexity

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);
    }

OUTPUT

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

解决方案

Whoa!Whoa! Wait.You are confusing two things.
One is running time which is the actual running time of a program on an instance of input.
Second is time complexity which is how the running time grows as input size grows.

A program which is O(N^2) can run much faster than a code which is O(NlogN) in practise.This is because the inputs may be mostly average cases, however the Big-Oh analysis is meant only for worst case analysis.This is because Big-Oh does not tell about actual running time(which may depend on nature of input(best case/worst case), details of actual implementation).Big-Oh only gives us a guarentee that an algorithm will run no worse than a constant times that function.

You can read my answers here to clarify these.

So when we say bubble sort/insertion sort is O(N²), we mean to say that that the running time in the worst case scenario is no larger than a constant times N^2.Realize that this is indeed the case for the two algorithms.

If you still have confusion please feel free to ask.

这篇关于为什么会冒泡排序和插入排序相同，即O（N ^ 2）的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！