5

私は Java SE 7 のヒントを学んでいます。次のような声明を読みましたArrayList。

  • アクセスは一定時間で行われます。
  • 挿入/削除は線形時間で実行されます。

一定の線形時間アクセスとは何ですか?

4

3 に答える 3

11

一定時間とは、各操作の実行にかかる時間のハード バウンドがあることを意味します。

線形時間とは、時間が長いほどArrayList(含まれるオブジェクトが多いほど)、操作にかかる時間が長くなることを意味します。接続は線形です。つまり、time(op) <= CONST * #elements

複雑さの分析では、これをBig O 表記と呼び、線形時間はO(n)、定数時間はO(1)

その理由は次のとおりです。

  • アクセスはプレーンな配列アクセスで、RAM マシン (out PC など) では一定時間で行われます。
  • 挿入/削除 - 最後の要素にない場合は、次のすべての要素をシフトする必要があります: (挿入には右にシフトし、左に削除する必要があります) - したがって、挿入/削除を実行するには、実際には直線的な数の OP が必要です (ただし、それは最後の要素です）
于 2012-11-08T12:12:25.517 に答える
10

意味は次のとおりです。

  • 定数は、リストの長さに関係なく、時間が常に同じであることを意味します。

    [ Big-O 記法では定数時間はO(1)とも呼ばれる]

  • 線形は、リストが大きくなればなるほど時間がかかることを意味しますが、線形の方法であるため、たとえば、20 個の要素を含むリストで線形操作を実行するには、10 個の要素を含むリストに必要な時間の 2 倍の時間がかかります。 .

    [ Big-O 記法では線形時間はO(n)とも呼ばれる]

    正確な説明: アルゴリズムを比較すると、通常は最悪の場合のパフォーマンスが提供されるため、必要な時間が線形以下であることを意味します。

あなたの場合、 List の実装は次のような配列に基づいています(したがってArrayListという名前):

Java ArrayList の説明

プログラムがリストの最初の要素がどこにあり、各セルの大きさを知っている場合、次のような単純な計算を使用してn番目の要素を直接取得できるため、アクセス時間は一定です。

element_n_cell = element_1_cell + (cell_size * n)

挿入と削除は、次の 2 つの理由から時間がかかります。

  1. 位置に要素を挿入または削除する場合、後続のすべての要素をシフトする必要があります。

  2. 配列のサイズは変更できないため、新しい ArrayList をインスタンス化すると、Java は事前に定義された長さs の配列を作成し、収まる限り同じ配列を使用します。(s+1)番目の要素を追加すると、プログラムはより大きな配列を作成し、すべての要素を新しい配列にコピーする必要があります。

于 2012-11-08T12:13:21.913 に答える