1

私は基本的にサイズから10個のランダムな配列を作成します:8000,16000,32000,64000,128000,256000

つまり、サイズ 8000 の 10 個の配列、サイズ 16000 の 10 個の配列などがあります。

これらにはすべて、0 から配列サイズまでの範囲の乱数が取り込まれます。

シェルソートの実装があります：

public static void sortMyArray(int[] a){
for (int gap = a.length / 2; gap > 0; gap = (gap / 2)) {
    for (int i = gap; i < a.length; i++) {
        int tmp = a[i];
        int j = i;
        for (; j >= gap && tmp < (a[j - gap]); j -= gap) {
            a[j] = a[j - gap];
        }
        a[j] = tmp;
     }
}
}

ギャップがgap = a.length / aの場合。長さ 私は単に挿入ソートを持っています。これらの配列をソートする時間は次のとおりです。

Number of Elements  Milliseconds
8000                13
16000               53
32000               217
64000               828
128000              3311
256000              13352

つまり、これはおおよそ O(N^2) です。要素数が 2 倍になると、解決時間はほぼ 4 倍になります。

ただし、 gap = a.length / 2 を使用すると、次のような値が得られます。

Number of Elements  Milliseconds
8000                2
16000               2
32000               4
64000               10
128000              25
256000              60

これは O(N) よりも優れていると思いますか? これはどのように可能ですか？Windows からプロセッサをシャットダウンしようとしました。また、コンピュータを 1 つのプロセッサだけで実行しようとしましたが、値はまだ論理的ではありませんでした。

興味がある場合は、私の完全なコードを次に示します。

int[] arraySizes = new int[]{8000,16000,32000,64000,128000,256000};
Random rn = new Random(1);

for(int i=0;i<arraySizes.length;i++){
    int[] arrayToBeSorted = new int[arraySizes[i]];
    System.out.println("Solving array with: " + arraySizes[i] + " elements with first sorting algorithm.");
    for (int c = 0; c < 10; c++) {
        for(int t=0;t<arraySizes[i];t++){
            int randomNumber = rn.nextInt(arrayToBeSorted.length);
            arrayToBeSorted[t] = randomNumber;
        }
        Long initialTime = (new Date().getTime());
        sortMyArray(arrayToBeSorted);
        Long finalTime = (new Date().getTime());
        System.out.println("Time in milliseconds:" + (finalTime - initialTime));
    }
}
4

1 に答える 1

2

あなたの実装は正しいように見えますが、あなたの仮定はそうではありません。

関数の複雑さが O(n^2) で実行時間が 3311 秒の場合、複雑さが O(n) の他の関数は同じデータに対して約 57 秒実行する必要があると想定します。

ただし、大きな O 表記は、実際の実行時間ではなく、関数の成長率についてのアイデアを提供します。したがって、成長率に応じてさまざまな機能の実行時間を単純に比較することはできません。

于 2013-05-16T05:43:58.373 に答える