algorithm - シェルソートの時間の複雑さ?

Question

まず、これが私のシェルソートコードです（Javaを使用）：

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を参照)。このレベルの効率が私のコードで実現されているとは思えません。ヒューリスティックを追加した場合は、そうですが、現状では違います。

そうは言っても、今の私の主な質問は、シェルソート実装の Big O 時間の複雑さを計算するのが難しいということです。最も外側のループは O(log n)、中間のループは O(n)、最も内側のループも O(n) と特定しましたが、内側の 2 つのループは実際には O( n) - それらはこれよりはるかに少ないでしょう - どのようなものであるべきですか? 明らかに、このアルゴリズムは O((log n) n^2) よりもはるかに効率的に実行されるためです。

私は非常に迷っているので、どんなガイダンスも大歓迎です！：P

Answer 1

実装の最悪のケースは Θ(n^2) であり、最良のケースは O(nlogn) であり、シェルソートに適しています。

最良のケース ∊ O(nlogn):

最良のケースは、配列が既にソートされている場合です。これは、内側の if ステートメントが決して true にならないことを意味し、内側の while ループを一定時間の操作にします。他のループに使用した境界を使用すると、O(nlogn) が得られます。O(n) の最良のケースは、一定数のインクリメントを使用することによって達成されます。

最悪のケース ∊ O(n^2):

各ループの上限を指定すると、最悪の場合に O((log n)n^2) が得られます。ただし、ギャップ サイズ g の別の変数を追加します。内側の while で必要な比較/交換の数は <= n/g になりました。中間 while の比較/交換の回数は <= n^2/g です。各ギャップの比較/交換回数の上限を合計します: n^2 + n^2/2 + n^2/4 + ... <= 2n^2 ∊ O(n^2)。これは、使用したギャップの既知の最悪の場合の複雑さと一致します。

最悪のケース ∊ Ω(n^2):

偶数に配置されたすべての要素が中央値よりも大きい配列を考えてみましょう。奇数要素と偶数要素は、最後の増分 1 に達するまで比較されません。最後の反復に必要な比較/交換の回数は Ω(n^2) です。

Answer 2

挿入ソート

分析すれば

static void sort(int[] ary) {
    int i, j, insertVal;
    int aryLen = ary.length;
    for (i = 1; i < aryLen; i++) {
        insertVal = ary[i];
        j = i;
        /*
         * while loop exits as soon as it finds left hand side element less than insertVal
         */
        while (j >= 1 && ary[j - 1] > insertVal) { 
            ary[j] = ary[j - 1];
            j--;
        }
        ary[j] = insertVal;
    }
}

したがって、平均的なケースでは、while ループは途中で終了します。

つまり、1/2 + 2/2 + 3/2 + 4/2 + .... + (n-1)/2 = シータ((n^2)/2) = シータ(n^2)

2 で除算してもそれ以上の違いはありませんが、ここでは (n^2)/2 を達成しました。

シェル ソートは、n/2、n/4、n/8、....、2、1 のようなギャップを使用した挿入ソートに他なりません。これは、挿入ソートのベスト ケースの複雑さ (つまり、ループの終了中) が発生し始めることを利用することを意味します。挿入要素の左側に小さな要素が見つかるとすぐに、合計実行時間になります。

n/2 + n/4 + n/8 + n/16 + .... + n/n = n(1/2 + 1/4 + 1/8 + 1/16 + ... + 1/n ) = nlogn (調和級数)

したがって、その時間の複雑さは n(logn)^2 に近いものです。