java - ArrayList の先頭に要素を追加する時間の複雑さは?

Question

この配列に n 要素を持つ ArrayList があり、最初に要素を追加するとします。

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

この操作の時間計算量はどのくらいになりますか?

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

また

Javaの学習を始めたばかりで、次の文を見ました

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

ここでの「支持」とはどういう意味ですか? ありがとうございました！

Answer 1

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

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

末尾への追加は、複数の挿入で償却される O(1) です。

Answer 2

ArrayList.add(0, element)線形時間がかかりますが、非常に高速に使用できるため、定数は非常に低くなりますSystem.arraycopy。