爲什麼氣泡排序和插入排序的性能相同，即O（n^2）

我做了以下代碼來檢查氣泡排序和插入排序所需的迭代次數和交換次數。儘管（指下面的代碼）插入排序做了字面上的一半迭代和相同數量的掉期相比，冒泡排序，然後怎麼來都具有相同的BIG-O複雜爲什麼氣泡排序和插入排序的性能相同，即O（n^2）

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

來源

2013-07-09 Amit

Big-O描述輸入大小增加時的行爲。您的測試只包含一個固定大小的數組，因此與Big-O分析無關。此外，在大O分析中忽略了常量因素，所以插入排序完全可能在操作次數上「完成一半」，而仍然具有與泡沫排序相同的Big-O複雜性。 – Mankarse

哇！哇！等等，你混淆了兩件事。
一個是運行時間這是一個程序在輸入實例上的實際運行時間。
其次是時間複雜度這就是隨着輸入大小的增長，運行時間如何增長。

一種程序，其是O（N^2）可以運行比爲O（NlogN）在practise.This是因爲輸入可以是大多平均情況下，但是在大哦分析只是意味着一個碼快得多對於最壞情況的分析。這是因爲Big-Oh沒有告訴實際的運行時間（這可能取決於輸入的性質（最好的情況/最壞的情況），實際的實施細節）。大哦只給我們一個保證一個算法的運行速度不會低於該函數的常數倍。

你可以閱讀我的答案here來澄清這些。

因此，當我們說冒泡排序/插入排序是O（N 2 ），我們的意思是說，在最壞的情況下的運行時間是不超過一個常數乘以N^2.Realize較大那兩種算法的確如此。

如果您仍然有困惑，請隨時詢問。

來源

2013-07-09 10:39:09 Aravind

你解釋得很好，謝謝你。你能指點我一些文章/書籍，我可以閱讀更多關於算法和計算它的複雜性 – Amit

我很難找到好的文章，最好的方法是嘗試自己解決它，如果你有麻煩，你可以在這裏問。這就是我學習的方式。如果你有數學傾向，你可以閱讀CLRS的章節（書名：算法簡介） – Aravind

實際上，你經常會發現人們通過記號分析最壞情況，最佳情況和平均情況。很好的澄清，但。 –

在在第i次迭代中進行氣泡排序，你有ni-1內部迭代（n^2）/ 2總數，但是在插入排序中，你在第i步有最大i次迭代，但平均爲i/2，因爲你可以更早地停止內部循環，當你找到當前元素的正確位置後。所以你有（從0到n）/ 2這是（n^2）/ 4總共;

這就是爲什麼插入排序比氣泡排序更快的原因。

來源

2013-07-09 10:09:00

我不是辯論插入排序更快，我問是否更快與相似的交換次數，然後如何都有類似BIG-O – Amit

它可能會讓你感到困惑，因爲你對BIG-O表示有什麼錯誤的想法。 –

請記住，符號只是表示算法如何隨n增長而行爲。一個線性因素總是從那個下降。所以它並沒有說明一個算法是否快速，它只是說明了在增加n時需要花費更多時間才能完成的因素。

來源

2013-07-09 11:32:23

爲什麼氣泡排序和插入排序的性能相同，即O（n^2）

回答

相關問題