Shell排序的時間複雜度？

Question

首先，這裏（用Java）我Shell排序代碼：

public char[] shellSort(char[] chars) { 
    int n = chars.length; 
    int increment = n/2; 
    while(increment > 0) { 
     int last = increment; 
     while(last < n) { 
      int current = last - increment; 
      while(current >= 0) { 
       if(chars[current] > chars[current + increment]) { 
        //swap 
        char tmp = chars[current]; 
        chars[current] = chars[current + increment]; 
        chars[current + increment] = tmp; 
        current -= increment; 
       } 
       else { break; } 
      } 
      last++; 
     } 
     increment /= 2; 
    } 
    return chars; 
} 

這是一個正確實施殼牌的排序（忘記了現在大概最有效的差距序列 - 例如，1,3,7,21。 ..）？我問，因爲我聽說Shell Sort的最佳時間複雜度是O（n）。 （見http://en.wikipedia.org/wiki/Sorting_algorithm）。我無法看到我的代碼實現了這種效率水平。如果我給它增加了啓發式，那麼是的，但是按現在的樣子，沒有。

這就是說，我現在的主要問題 - 我難以計算我的Shell排序實現的大O時間複雜度。我確定最外層循環爲O（log n），中間循環爲O（n），最內層循環也爲O（n），但我意識到內部兩個循環實際上不會是O n） - 他們會比這少得多 - 他們應該是什麼？因爲很明顯，這個算法比O（（log n）n^2）運行得更有效率。

任何指導都非常感謝，因爲我很迷茫！ ：P

Answer 1

您實現的最壞情況是Θ（n^2），最好的情況是O（nlogn），這對於shell排序是合理的。

最好的情況εO（nlogn）：

最好情況下是當陣列已經排序。這意味着內部if語句永遠不會是真實的，從而使內部while循環持續一段時間的操作。使用你用於其他循環的界限給出O（nlogn）。 O（n）的最好情況是通過使用恆定數量的增量達到的。

最壞的情況ε爲O（n^2）：

鑑於你的上限爲每個Ø得到循環（（log n）的N^2）的最壞情況。但爲間隙尺寸g添加另一個變量。內部所需的比較/交換次數現在爲< = n/g。中間比較/交換的數量爲< = n^2/g。將每個空位的比較/交換次數的上限加在一起：n^2 + n^2/2 + n^2/4 + ... < = 2n^2εO（n^2）。這與您使用的差距的已知最壞情況複雜度相匹配。

最壞的情況εΩ（N^2）：

考慮陣列，其中所有偶數位置的元素比中值大。在我們達到最後一個增量1之前，不會比較奇數和偶數元素。最後一次迭代所需的比較/交換次數爲Ω（n^2）。