爲什麼插入排序的最佳情況是O（n）＆not O（n^2）？

我很難理解爲什麼最好的插入排序在o（n）？爲什麼插入排序的最佳情況是O（n）＆not O（n^2）？

 for (int i = 0; i < size; i++) { 

       for (int j = i; j > 0; j--) { 
        int k = j-1; 
         if(a[j] < a[k]){ 
          int temp = a[j]; 
          a[j] = a[k]; 
          a[k] = temp; 
         } 

       } 
    }

讓我們考慮一個例子初始陣列[1,2,3,4,5]尺寸= 5 第一環路會從i = 0到大小 - 1 和第二環路將去從i到1但讓我們假設，內for循環也從0變爲大小 - 1內的for循環也執行第（n-1）相似的外次循環我同意將沒有互換但會有比較的，&它換句話說將完全等於未排序數組？則n-1（外環）* N - 1（內循環）= N^2 - N + 1 = O（N^2）
任何一個可以解釋我在哪兒錯了？

來源

2013-01-19 zukes

沒有用於計算最佳案例複雜度的有用應用程序。話雖如此，當數組已被排序時，您的算法會浪費時間。每次'a [i + 1]> = a [i]'都可以跳過內部循環。 –

這是插入排序？ –

@n.m。，你說最好的案例沒有應用，大概最好的案例或接近最佳案例的案例不會經常出現在隨機數據中，但是隨後你會繼續推薦代碼變化，這些變化只有在這些數據方面纔有意義。在某些情況下，人們的數據可能處於近似排序的順序，在這種情況下，運行時間將比O（N^2）更接近O（N）。 – Richard

你的代碼總是運行在O（n^2）。當你找到元素應該在的地方時，你必須打破內部循環。

來源

2013-01-19 14:19:15 Amtrix

這裏有一種實現插入排序的方法。

取一個輸入列表和一個最初爲空的輸出列表。

通過輸入列表迭代和每個項目放置到輸出列表上的適當位置。通過遍歷輸出列表來找到合適的位置，從第一個元素開始。

現在，如果你的輸入已經排序，然後將插入點永遠是在輸出列表的開頭或結尾。第一種可能性對應於最佳情況;第二個對應於最壞的情況。

例如，我的輸入數據爲：4 3 2 1

然後輸出列表構建爲：

由於着眼於第一元件只消O（1），則時間複雜度在輸入的大小，或O（N）。

來源

2013-01-19 14:17:35 Richard

他正在使用一個數組，而不是一個列表。 – Gumbo

這裏的區別很微不足道@Gumbo。 – Richard

插入排序的最佳情況是數值已經按升序排列。你所描述的是其最壞的情況，其中對於每個插入的值，必須移動所有先前插入的值，導致產生Ο（n^2）。 – Gumbo

最佳插入的情況下，排序是爲O（n）當陣列已經排序。

但是你的算法仍然需要爲O（n^2）排序情況。所以你應該只在條件失敗時進入第二個循環。這種方式在排序列表的情況下，你將永遠不會進入你的內部循環。

檢查下面的鏈接：http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

http://en.wikipedia.org/wiki/Insertion_sort

來源

2013-01-19 14:28:32

最好的情況也在Ω（n）中，因此也在Θ（n）中。 – Gumbo

起初，這似乎並不爲插入排序正確的代碼。看起來你正在以相反的方式使用冒泡排序代碼。
在插入排序代碼中，並不是用每個大元素都替換掉一個小元素，而是在所有大元素之前掠過，只有當我們處於沒有元素的時候或者沒有更多的大元素，那麼我們將小元素放置在該位置並移動/移動所有其他後續元素。

作爲O（n）時間的一部分：
讓我們考慮一個由五個已排序元素組成的數組 - arr [11,13,15,17,19]。我們從第一個位置移動到最後一個位置。
第1步：以元素11，因爲它是第一個元素，我們保持它原樣。
步驟2：取元件13，尋找之前它落在元件（即元件11），如圖13> 11，因此不再需要用於在看該前11.
步驟3落入元素：取元素15，查找落在它之前的元素（即元素13），因爲15> 13，因此不需要再看到之前的元素13.
步驟4：取元素17，查找元素落在它之前（即元素15），因爲17> 15，因此不再需要查看落在15之前的元素。
步驟5：取元素19，尋找之前（即17元），即下降因素，因爲19> 17，因此不再需要爲尋找我們看到，五個已排序的元素，我們只需要前17

落在元素5個比較，因此對於'n'個排序元素，我們只需要O（n）比較。

我希望上面的例子澄清你的疑問。

來源

2015-06-11 06:46:40

改變你的方法有這個休息條件，你會得到最好的情況下的複雜度爲O（n）。

void insertionSort0(List<Integer> list) 
{ 
    int loop=0; 
    for(int i=1;i<list.size();i++) 
    { 
     int target=(Integer)list.get(i); 
     int pos=0; 

     for(int j=i-1;j>=0;j--) 
     { 
      loop++; 
      if((Integer)list.get(j)>target) 
      { 
       list.set(j+1, (Integer)list.get(j)); 
       pos=j; 
      } 
      else 
      { 
       break; 
      } 


     } 


      list.set(pos, target); 

    } 
    System.out.println("loop in for insertion sort" +loop); 
}

來源

2015-06-27 06:41:28 Onki

考慮以下實現插入排序的：

for (i=1; i<n; i++) { 
     j=i; 
     while ((j>0) && (s[j] < s[j-1])) { 
      swap(&s[j],&s[j-1]); 
      j = j-1; 
     } 
    }

任何排序算法最好的情況是，當輸入已經是排序順序。在這種情況下，while循環中的條件總是返回false，因此它僅迭代for for循環，以O（n）時間複雜度的線性時間執行作業。

來源

2015-08-31 00:16:18

爲什麼插入排序的最佳情況是O（n）＆not O（n^2）？

回答

相關問題