complexity-theory - 複雑さとビッグオー

Question

次の 2 つのアルゴリズムの最悪のケースの時間計算量は、アイテムにサイズ変更の必要がないほど十分な未使用スペースがあると仮定すると? 私の最初の推測では、インデックス [0] に新しい要素を追加するためにすべての要素をシフトする必要があるため、A の実行は遅くなるでしょう。最悪の場合、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));

Answer 1

それは、アイテムを格納するために使用される基本的なデータ構造に大きく依存します。リンクされたリストを使用する場合、A のような挿入には一定の時間がかかります。つまり、O(1) ですが、配列を使用する場合は、すべての要素を 1 桁左にシフトしてスペースを空ける必要があるため、O(n) になります。新しいアイテム。したがって、連結リストが使用されている場合はループの複雑さが O(n) になり、配列が使用されている場合は O(n^2) になります。

B の場合、add 関数をどのように実装するかが明確でないため、その複雑さについては何も言えません。連結リスト、配列、バランス ツリーを使用する場合は、複雑さが異なります。