ArrayListの先頭に要素を追加する時間の複雑さは何ですか？

は、私がこの配列にn個の要素を持つArrayListのを持っていると言う、と私は先頭に要素を追加します。ArrayListの先頭に要素を追加する時間の複雑さは何ですか？

myArrayList.add(0,'some value');

何この操作の時間複雑になりますか？

Java Docはこれを指定しません。

また

私はJavaの学習を開始し、私はここで '裏打ちされた' どういう意味の文

An ArrayList in Java is a List that is backed by an array.

を見ましたか？ありがとうございました！

出典

2013-05-27 lakeskysea

これは 'ArrayList'が実装であることを意味し、' List'はインターフェースです。 –

ArrayListは技術的には意味のある配列です。 System.arraycopyメソッドを使用して要素の追加と削除を処理します。この場合、0〜0（空）と（0〜n）の2つの配列が作成されます。次に、長さ+ 1の新しい配列を作成し、それらをまとめて結合し、それぞれのインデックスに新しい要素を入れます。 –

配列の先頭に要素を追加するのはO（n）です。既存の要素をすべて1つずつシフトする必要があります。

アレイリスト内のすべての要素は、連続した配列に格納されます。配列の現在のサイズよりも多くの要素を追加すると、新しい要素に合わせて自動的に拡張されます。

最後に追加するとO（1）が複数回挿入されて償却されます。

出典

2013-05-27 17:27:23 gkamal

私はO（n）が普通のケースだと知っていますが、実際にJavaがこのケースでいくつかの魔法を実行するかどうかを尋ねていました（Louis Wassermanのようなもの）？十分に明確でないことを申し訳ありません！ – lakeskysea

「このケース」はどういう意味ですか？ –

@LouisWasserman申し訳ありませんが、私は 'この操作'を意味します。この操作には通常O（n）が必要ですが、Javaの実装にArrayListの先頭に要素を追加する「スマートな方法」があるかどうかは疑問でした。リニアな時間がかかる理由をちょっと説明してもらえますか？ – lakeskysea

ArrayList.add(0, element)は線形時間がかかりますが、急激な速さSystem.arraycopyを使用できるため、定数は非常に低くなります。 O（nは）：最初からリストを構築し、次の時間で始まる実行する要素の多くを追加すること

出典

2013-05-27 17:27:29

。
リストの最後にすべての要素を追加し、 Collections.reverse(list)を呼び出すと、線形時間：O（n）で実行されます。

出典

2017-07-05 05:25:37 Roland

ArrayListの先頭に要素を追加する時間の複雑さは何ですか？

答えて

関連する問題