1

何かを追加しようとするとサイズが 2 倍になる拡張配列があるとしますが、それはいっぱいです。

スライド「償却: ベクトルの拡大」の下部によると、1 つの要素を追加するための最悪のケースの時間は、N ではなく 2N ですか? どうしてこれなの？

N個の要素を新しいダブルサイズの配列にコピーするにはN個の時間がかかるため、Nになると思いました。

たとえば、サイズ 4 の塗りつぶされた配列に要素を 1 つだけ追加するとします。次のようになります。

  1. サイズ 8 (4 の 2 倍) の新しい配列を作成します。
  2. 元の配列のすべての要素を新しい配列にコピーします (4 回コピー)。
  3. 新しい配列の 5 番目の要素を追加要素に設定します (1 回コピー)。

では、要素を 5 回コピーすると、2N ではなく N + 1 になりますか?

4

1 に答える 1

1

拡張配列に要素を追加するために必要な操作は O(2N) です。これは、最初に配列全体を調べて、O(N) で空き領域をチェックする必要があるためです。これは最悪のケースであるため、新しい配列を作成し、コンテンツ全体を最初の配列から新しい配列に O(N) でコピーする必要があります。両方の操作を組み合わせると、O(2N) になります。

配列の長さについて考えるとき、長さは実際には配列用に予約されているサイズであり、内部の要素の数ではありません。そのため、要素数をどこにも保存しなかった場合は、配列全体をループして空のスペースを探す必要があります。「空のスペース」について話しているのは、要素が追加されただけで、配列内で何も削除されなかったとは述べられていないためです。

于 2013-10-14T21:23:33.270 に答える