75

ArrayListjavaの配列またはリストですか? get 操作の時間計算量はどれくらいですO(n)かO(1)?

4

6 に答える 6

126

ArrayListJavaのは、Listによってサポートされるarrayです。

メソッドはget(index)一定時間、O(1)、操作です。

の Java ライブラリから直接取り出したコードArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

基本的に、バッキング配列から直接値を返すだけです。( RangeCheck(index))も一定時間)

于 2010-02-02T08:10:42.957 に答える
23

その実装は配列で行われ、取得操作は O(1) です。

javadoc 言います：

size、isEmpty、get、set、iterator、および listIterator 操作は一定時間で実行されます。追加操作は償却定数時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。他のすべての操作は線形時間で実行されます (大まかに言えば)。定数係数は、LinkedList の実装に比べて低くなります。

于 2010-02-02T08:09:11.353 に答える
12

誰もがすでに指摘しているように、読み取り操作は一定時間 - O(1) ですが、書き込み操作はバッキング アレイ、再割り当て、およびコピーでスペースが不足する可能性があるため、O(n) 時間で実行されます。 、ドキュメントが言うように：

size、isEmpty、get、set、iterator、および listIterator 操作は一定時間で実行されます。追加操作は償却された定数時間で実行されます。つまり、n 個の要素を追加するには O(n) 時間が必要です。 他のすべての操作は線形時間で実行されます (大まかに言えば)。定数係数は、LinkedList の実装に比べて低くなります。

実際には、バッキング配列は容量が使い果たされるたびに 2 倍になるため、数回追加するとすべてが O(1) になります。したがって、配列が 16 で始まり、いっぱいになると、32、次に 64、128 などに再割り当てされるため、問題なくスケーリングされますが、大きな再割り当て中に GC がヒットする可能性があります。

于 2010-02-02T08:18:53.637 に答える
5

分かりやすく言うと、これListは配列に裏打ちされたものです。はい、時間計算量get()は O(1) です。

于 2010-02-02T08:10:31.660 に答える
0

arraylist は基本的に配列の実装です。そのため、CRUD 操作の時間の複雑さは次のようになります。

get/read :  O(1) since you can seek the address directly from base

remove/delete : O(n) why ? Because once we delete the element at index, then we need to move the after values one by one to the left. 

add : O(1) becuase you always add the end of the array - next free address available.

update : O(1) since you are just changing the value but nothing value moving....across the array.
于 2020-05-15T23:25:20.420 に答える