for (int i =0; i < n; i++){
lst.add(lst.size()/2,3*i);
}
for ループは o(n) を取ると思っていましたが、ArrayList と LinkedList を使用した場合の add(j,t) の違いは何なのかはっきりしませんでした..ありがとう!
質問する
82 次
2 に答える
3
an のいくつかのスロット k に挿入する場合ArrayList、k は O(1) ですが、k の後に各要素をプッシュバックする必要があります。これは O(n) です。ただし、ArrayList配列のサイズを変更する必要がある状況を考慮に入れる必要があるため、 an の最後に挿入すると償却されます。
a のLinkedList場合、位置 k の要素への参照がない限り、リストを反復処理してその位置を見つける必要があります。これは O(n) ですが、実際の挿入は常に O(1) です。
于 2013-11-03T21:50:50.987 に答える
1
の場合LinkedList<E>:
add(int インデックス, E 要素) は O(n)
の場合ArrayList<E>:
add(int index, E element) は O(n - index) 償却されますが、O(n) 最悪の場合 (上記のように)
ソース：
于 2013-11-03T21:55:12.167 に答える