配列リストを反復する時間の複雑さ

Question

私は反復する配列リストを持っています。各反復では私は1つの要素を取得するためにget()を呼び出し、その項目はいくつかの条件に合格した場合、それは私が時間の複雑さがここには何かわからないadd()

List<Item> items = new ArrayList<Item>(); 
List<Item> lessItems = new ArrayList<Item>(); 
for(int index = 0; index < items.size(); index++){ 
    Item toCheck = items.get(i); 
    if(toCheck meets some condition){ 
     lessItems.add(toCheck); 
    } 
} 

を使用して新しい配列リストに追加されます。私はすべてのアイテムにget（）を呼び出すので、それはO（n）です。次に、潜在的にすべてのアイテムにadd（）を呼び出して、別のO（n）があるようにします。これはあまり確かではありません。

Answer 1

Big-Oおよび類似の表記は、時間の複雑さに関する漸近的な境界です。それらは数値係数を破棄し、入力のサイズの関数として実行時間を見積もるために使用されます。

したがって、2*n、3*nなど。 O(n)、2*nlog(n),3*nlog(n)などと表される。 O(nlog(n))と表されます。

追加（）操作は、この場合の唯一の要素を挿入するので、そのランタイムは約ある、(some small constant)k*1、すなわちj*n、又はO(n)に、(some constant)j*(n+some constant(k))として総実行時間を与えます。

この場合、すべてのそのような同様の場合において、N乗じ任意定数Kは、ランタイムは、入力のArrayListのサイズに比例して変化意味O(n)として表されることになります。

Answer 2

他の回答はすべてです。ここではが間違っています。

1. itemsリストを反復処理するためのあなたの最初のループ：他の人が言ったように、通常の配列にそれがO(n)になります：複雑さは、リストlessItemsの最後に各項目を挿入しO(n)
2. です。しかし、JavaはArrayListのためにamortized arrayを使用して実装します。これは、配列の最後に挿入するとき、アルゴリズムのコストがAmortized O(1)であることを意味します。または、あなたが言うことができるO(1)

あなたのコードの複雑さはO(n) * amortized O(1)です。

dynamic array

追加注1：要するにO(n)

別の参照である

総複雑性はO(N^2)なるようにアレイの端部に挿入する複雑さは、O(N)ある場合、ありませんO（2 * N）と答えました。 1 + 2 + 3 + ...+ n = n*(n+1)/2

addtionalの注2：

official documentなどの状態：

サイズ、のisEmpty、取得、セット、イテレータ、および反復子の操作が を実行して挿入するための総複雑さは次のようになりますので、一定の時間内に。加算演算は償却定数時間, で実行されます。つまり、n個の要素を追加するにはO（n）時間が必要です。その他のすべての操作は、線形時間（大まかに言えば）で実行されます。定数因子 は、LinkedListの実装に比べて低いです。プログラムが追加したときに、ソースコードは、言ったように

private void ensureExplicitCapacity(int minCapacity) { 
     modCount++; 

     // overflow-conscious code 
     if (minCapacity - elementData.length > 0) 
      grow(minCapacity); 
    } 

private void grow(int minCapacity) { 
     // overflow-conscious code 
     int oldCapacity = elementData.length; 
     int newCapacity = oldCapacity + (oldCapacity >> 1); 
     if (newCapacity - minCapacity < 0) 
      newCapacity = minCapacity; 
     if (newCapacity - MAX_ARRAY_SIZE > 0) 
      newCapacity = hugeCapacity(minCapacity); 
     // minCapacity is usually close to size, so this is a win: 
     elementData = Arrays.copyOf(elementData, newCapacity); 
    } 

：

追加注3：ここでは

は、私は公式のJavaのソースコードから取られているgrow方法の論理です配列のサイズを現在の容量よりも大きくする要素は、Arrayが拡張されます。成長した配列の新しいサイズは次のようになります。

int newCapacity = oldCapacity + (oldCapacity >> 1); 

これは、挿入はamortized O(1)

Answer 3

あなたが繰り返しをやっているのである作るトリックであり、それはO（n）とのです。

また、OであるArrayListの、に項目を追加（1）（Amortized）

インデックスを取得しているにもO（1）です。

O（n）回の操作で、O（1）の操作がO（n）になる予定です。