動的配列は、容量に達すると自動的にサイズを変更するデータ構造です。 償却コストの把握は、複数の操作で効率性を評価することができます。

償却費とは?

償却費は、作業の順番に1回あたりの平均コストです。 これにより、多くの安価な操作を配信することで、時折節約のコストが高くなります。

動的配列操作

動的配列の一般的な操作には、インサート、削除、および再サイズが含まれます。 エンドのインサートは通常、容量を超えたときに再サイズをトリガーする最も頻繁に動作する。

償却費の計算

要素を投入すると、配列はサイズが大きく倍増します。再サイズ化のコストは、既存の要素を新しい配列にコピーすることを含みます。再サイズは高価ですが、それは不十分です。

例えば、配列が容量1で始まると、複数のインサートを上回る再サイズ化のシーケンスが以下のようにまとめられます。

  • インサート1要素:コスト1
  • インサート2nd要素:サイズ変更(コスト1)、合計コスト2
  • インサート3rd要素:サイズ(コスト2)、合計コスト3
  • インサート4番目の要素:リサイズ(コスト4)、合計コスト4

インサートの合計コストは2nに比例して、インサートあたり約O(1)の償却費をします。