9

なぜ挿入ソートの最良のケースがo（n）にあるのか理解するのに苦労していますか？

     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になり、2番目のループはiから1になりますが、内側のforループも0からサイズ-1まで、言い換えると、内側のforループも外側のforループと同様に（n-1）回実行されます。スワップはありませんが、比較はあります。ソートされていない配列とまったく同じになりますか？次に、n-1（外側のループ）* n --1（内側のループ）= n ^ 2-n + 1 = O（n ^ 2）
誰でも、どこが間違っているのか説明できますか？

4

6 に答える 6

5

コードは常に O(n^2) で実行されます。要素があるべき場所を見つけた時点で、内側の for ループを中断する必要があります。

于 2013-01-19T14:19:15.190 に答える
1

挿入ソートを実装する1つの方法は次のとおりです。

入力リストと最初は空の出力リストを取ります。

入力リストを繰り返し処理し、各項目を出力リストの適切な位置に配置します。最初の要素から始めて、出力リストをたどって適切な位置を見つけます。

これで、入力がすでにソートされている場合、挿入ポイントは常に出力リストの最初または最後になります。最初の可能性は、最良のシナリオに対応します。2番目は、最悪のシナリオに対応します。

たとえば、私の入力データは4 321です。

次に、出力リストは次のように作成されます。

4
3 4
2 3 4
1 2 3 4

最初の要素を見るのにかかる時間はO（1）だけなので、時間計算量は入力のサイズ、つまりO（N）になります。

于 2013-01-19T14:17:35.860 に答える
0

配列が既にソートされている場合、挿入ソートの最良のケースはO(n)です。

ただし、アルゴリズムはソートされた場合でも O(n^2) を使用します。したがって、条件が失敗した場合にのみ、2 番目のループ内に入る必要があります。このようにして、ソートされたリストの場合、内部ループ内には決して入りません。

以下のリンクを確認してください: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

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

于 2013-01-19T14:28:32.917 に答える
0

このブレーク条件を持つようにメソッドを変更すると、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-27T06:41:28.303 に答える