0

次の 2 つのアルゴリズムの最悪の場合の時間計算量は、アイテム (a ArrayList<Integer>) にサイズ変更の必要がない十分な未使用スペースがあると仮定すると、どれくらいになりますか? 私の最初の推測では、 index に新しい要素を追加するためにすべての要素をシフトする必要があるため、 A の実行は遅くなるでしょう[0]。BがO(N^2)最悪のケースだと思いますが、よくわかりません。

A.

for (int i = 0; i < N; i++)
    items.add(0, new Integer(i));

とB.

for (int i = 0; i < N; i++)
    items.add(new Integer(i));
4

3 に答える 3

1

あなたの質問がJavaに関するものである場合、最初のバージョンは遅く、O(N^2)あなたが言及したまさにその理由のために複雑さを持っていますが、Bは複雑さを持っていますO(N)。

于 2013-02-13T19:41:02.427 に答える
1

items実装 A は、配列が十分に大きいと仮定すると、次のように実装できます。

for (int i = 0; i < n; i++) {
    for (int j = items.size; j > 0; j++) {
        items[j] = items[j-1]; 
    }
    items[0] = i;
}

この場合に実行される操作の総数 (リストmの初期サイズであると仮定) は次のようになります。items

この複雑さはO(n 2 )です。

一方、オプション B は次のように実装できます。

for (int i = 0; i < n; i++) {
    items[items.size] = i;
    items.size++;
}

この場合に実行される操作の数は

これは複雑さO(n)を持っています

于 2013-02-13T20:17:40.960 に答える
0

Aでは、挿入ごとに、すべての項目を配列リストの内部配列の右側にシフトする必要があります。これは、操作を完了するためのO（n ^ 2）になります。2番目のケースでは、シフトは必要ないため、O（n）になります。Aでは、あなたはたくさんの不必要で高価な仕事をしています。

ご規定のとおり、内部配列のサイズは変更されていないと思います。

于 2013-02-13T19:41:00.873 に答える