ArrayList：指定された要素への挿入と挿入の比較

Question

Arraylistを考えてみましょう。内部的にはフルではなく、これまでに挿入された要素の数が分かっています。要素はソートされません。 ArrayListに含まれる要素の数に関係なく、高速な以下の操作を選択します。 （言い換えれば、実装するにはいくつかの指示が必要です）。 （必ずしもソートされていない）整数のアレイで

削除の最大値を求める指定されたインデックス

からデータを取得与えられたインデックス

で

挿入

挿入指定されたインデックス

指定されたインデックスの要素を置換する

特定の要素を検索する

指定されたインデックスで挿入を選択し、指定されたインデックスからデータを取得し、要素を置き換えるが、回答キーは挿入と表示されます。私が通常理解しているように、ArrayListでは、挿入操作ではすべての要素が左にシフトする必要があります。リストの始めにこれを行った場合、$ O（n）$時間の複雑さがあります。しかし、最後にやった場合、$ O（1）$になります。

私の質問がダウンになる：（1）いずれかの場合には、差が指定されたインデックスに挿入し、挿入の間があり、（2）の挿入のために、この特定の時間の複雑さを与えられたものを、それが

Answer 1

は、まずあなたが最初の方法を見れば今java.util.ArrayList

public boolean add(E e) { 
    ensureCapacityInternal(size + 1); // Increments modCount!! 
    elementData[size++] = e; 
    return true; 
} 

public void add(int index, E element) { 
    rangeCheckForAdd(index); 

    ensureCapacityInternal(size + 1); // Increments modCount!! 
    System.arraycopy(elementData, index, elementData, index + 1, 
        size - index); 
    elementData[index] = element; 
    size++; 
} 

1. で定義されたこれらの2つの方法を見てみましょう（ただ追加要素：ビッグO-表記の詳細については

   ）、それは十分な容量があるかどうかを確認し、がリストの最後に要素を付加します。
   十分な容量があれば、この操作には時間がかかります。それ以外の場合は、すべての要素を移動する必要があり、最終的に時間の複雑さはO(n)に増加します。

2. 2番目の方法では、indexを指定すると、そのインデックスの後ろにあるすべての要素がシフトされ、前者の方が前者の方が時間がかかるでしょう。

Answer 2

「速い」と考えている理由最初の質問についての答えはこれです：iを以下のすべての要素が一つの位置で右にシフトする必要がありますので、指定されたインデックスiで

• 挿入は、O(n)をとります。
• 一方、Java（ArrayList.add()）で実装されている単純な挿入は、要素が配列の末尾に追加されているため、シフトが不要なため、O(1)となります。

簡単な挿入が高速である理由は明らかです。余分な操作が必要ないため、時間は一定です。

Answer 3

は、（1）それが連続要素を何、もしあれば、差が指定されたインデックスに挿入し、挿入の間に存在すると

ArrayListの店舗。 ArrayListの末尾に追加すると、新しい要素をその末尾に追加する以外は、ArrayListを変更する必要はありません。したがって、この動作はO（1）であり、データ構造内でアクションを繰り返し実行したい場合に好ましい一定の時間をとる。

しかし、インデックスに要素を追加するには、何らかの方法で要素のための空き領域を作るためにArrayListが必要です。それはどうですか？挿入された要素に続くすべての要素は、新しい挿入のためのスペースを作るために一歩移動する必要があります。あなたのインデックスは、最初の要素とn番目の要素（包括的に）の間にあるものです。したがって、この演算は、せいぜいO（1）であり、最悪ではO（n）であり、nは配列のサイズである。大きなリストの場合、O（n）はO（1）よりかなり長い時間がかかります。

（2）の挿入のためのこの特定の時間の複雑性を与え、それは、「高速」であると考えられる理由

それはO（1）、又は時定数であるので、高速であると考えられます。時間の複雑さが本当に1回の操作であれば、可能な限り速く、他の小さな定数も高速であると見なされ、O（1）によって等しく表記されることがよくあります。しかし、操作の量は他のもののサイズに依存しない、あなたの例ではArrayListのサイズになります。しかしながら、一定の時間複雑度は大きな定数も含む可能性があるが、一般に、可能な限り最も速い時間複雑度とみなされる。これをコンテキストにするために、O（1）操作は、1000要素のArrayListで約1 * k回の操作を行い、O（n）操作は約1000 * k回の操作を行います。

Big-O表記は、アクションまたはプログラム全体が実行されるときに実行される操作の数を測定する基準として使用されます。 What is a plain English explanation of "Big O" notation?

Answer 4

ArrayListは内部的には、Array.copyOfを使用して、サイズが増加した新しい配列を追加時に作成しますが、元の内容はそのままです。 単純な追加（配列の最後にデータを追加する）であれ、最初の（0番目）のインデックスであれ、挿入は単純さを念頭に置いていれば、より高速でほとんどのデータ構造になりますのデータ構造。

唯一の違いは、単純な加算はトラバーサルを必要としないことですが、インデックスでの加算では、要素の左へのシフトが必要です。これは、System.arrayCopyを使用して、インデックスとデータを変更しながら、あるアレイを別のアレイにコピーします。

だから、単純な挿入は速く、次にインデックス付きの挿入です。