償却分析

コンピュータサイエンスにおいて、償却分析は、特定のアルゴリズムの複雑さ、つまり実行に要するリソース、特に時間やメモリの量を分析する方法です。償却分析の目的は、最悪の実行時間を見るのは悲観的すぎる場合があることです。代わりに、償却分析では、シーケンス内の操作の実行時間をそのシーケンスにわたって平均化します。^{[1] : 306}結論として、「償却分析は、最悪ケース分析や平均ケース分析 などの他の手法を補完する便利なツールです。」^{[2] : 14  [3]}

アルゴリズムの特定の操作では、特定の状況（入力パラメータ化やデータ構造の内容など）ではリソースに大きなコストがかかる可能性がありますが、他の状況ではそれほどコストがかからない場合があります。償却分析では、操作シーケンス全体にわたって、コストのかかる操作とコストのかからない操作の両方を考慮します。これには、さまざまなタイプの入力、入力の長さ、およびパフォーマンスに影響を与えるその他の要因を考慮することが含まれます。^[2]

償却分析は、当初は集約分析と呼ばれる手法から生まれましたが、現在は償却分析に含まれています。この手法は、1985 年の論文「償却計算複雑性」^[1]でRobert Tarjanによって初めて正式に導入されました。この論文では、一般的に使用されている確率的手法よりも有用な分析形式の必要性が取り上げられています。償却は当初、特にバイナリ ツリーや和集合演算を含むアルゴリズムなど、非常に特殊な種類のアルゴリズムに使用されていました。しかし、現在では広く普及しており、他の多くのアルゴリズムの分析にも使用されています。^[2]

償却分析では、どの一連の操作が可能かという知識が必要です。これは、操作間で状態が持続するデータ構造の場合に最もよく当てはまります。基本的な考え方は、最悪のケースの操作によって状態を変更し、最悪のケースが長期間にわたって再び発生しないようにすることで、コストを「償却」できるというものです。

償却分析を実行するための一般的な方法は、集計法、会計法、潜在法の3つです。これらはすべて正しい答えを与えます。どれを使用するかは、特定の状況に最も便利な方法によって異なります。^[4]

• 集計分析では、 n回の操作のシーケンスの総コストの上限T ( n )を決定し、償却コストをT ( n )/ nとして計算します。^[4]
• 会計方法は、各操作に実際のコストとは異なる可能性のある償却コストを割り当てる集計分析の形式です。初期の操作の償却コストは実際のコストよりも高く、実際のコストよりも低い償却コストを持つ後の操作の支払いに充てられる「クレジット」が蓄積されます。クレジットはゼロから始まるため、一連の操作の実際のコストは、償却コストから累積クレジットを差し引いた値に等しくなります。クレジットは負であってはならないため、償却コストは実際のコストの上限です。通常、多くの短期実行操作ではこのようなクレジットが少しずつ蓄積されますが、まれに長期実行操作ではクレジットが大幅に減少します。^[4]
• 潜在的方法は、保存されたクレジットがデータ構造の状態の関数（「潜在的」）として計算される会計方法の一種です。償却コストは、即時コストと潜在的変化を加えたものです。^[4]

Java やC++などのように、要素が追加されるにつれてサイズが大きくなる動的配列を考えてみましょう。サイズが 4 の動的配列から開始した場合、4 つの要素をプッシュすることができ、各操作には定数時間がかかります。しかし、その配列に 5 番目の要素をプッシュするには、配列が現在のサイズの 2 倍 (8) の新しい配列を作成し、古い要素を新しい配列にコピーしてから、新しい要素を追加する必要があるため、さらに時間がかかります。次の 3 つのプッシュ操作も同様に定数時間がかかり、その後の追加では配列サイズをもう一度ゆっくりと 2 倍にする必要があります。 ArrayListstd::vector

一般に、任意の初期サイズの配列に任意の回数プッシュすると、配列を 2 倍にするステップの時間は等比級数でに加算され、残りの各プッシュの定数時間も に加算されます。したがって、プッシュ操作あたりの平均時間は です。この考え方は、償却分析を使用して形式化し、より複雑なデータ構造に一般化できます。^[4]${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n)}$${\displaystyle O(n)/n=O(1)}$

以下は、FIFO データ構造であるQueueの Python3 実装です。

class  Queue : 
  # 2つの空のリストでキューを初期化します
  def  __init__ ( self ): 
    self . input  =  []  # キューに入れられた要素を格納します
    self . output  =  []  # キューから外された要素を格納します

  def  enqueue ( self ,  element ): 
    self . input . append ( element )  # 入力リストに要素を追加します

  def  dequeue ( self ): 
    if  not  self . output :  # 出力リストが空の場合
      # 入力リストのすべての要素を逆順に出力リストに転送します
      while  self . input :  # 入力リストが空でない場合
        self . output . append ( self . input . pop ())  # 入力リストから最後の要素をポップし、出力リストに追加します
    
    return  self.output.pop () #出力リストから最後の要素をポップして返します 

エンキュー操作は、入力配列に要素をプッシュするだけです。この操作は入力または出力の長さに依存せず、したがって一定時間で実行されます。

しかし、デキュー操作はより複雑です。出力配列にすでに要素が含まれている場合、デキューは定数時間で実行されます。そうでない場合、デキューは入力配列から出力配列にすべての要素を追加するのに⁠ ⁠時間がかかります。ここで、 ${\displaystyle O(n)}$n は入力配列の現在の長さです。入力からn個の要素をコピーした後、出力配列が再び空になるまでに、定数時間かかるn回のデキュー操作を実行できます。したがって、 n 回のデキュー操作のシーケンスをわずか⁠ ⁠${\displaystyle O(n)}$時間で実行できます。これは、各デキュー操作の償却時間が⁠ ⁠${\displaystyle O(1)}$であることを意味します。^[5]

あるいは、入力配列から出力配列に任意の項目をコピーするコストを、その項目の以前のエンキュー操作に課金することもできます。この課金方式では、エンキューの償却時間は 2 倍になりますが、デキューの償却時間は ⁠ ⁠ に短縮されます${\displaystyle O(1)}$。

• 一般的な用法では、「償却アルゴリズム」とは、償却分析によってパフォーマンスが良好であることが示されたアルゴリズムを指します。
• オンライン アルゴリズムでは、一般的に償却分析が使用されます。

• 「講義 7: 償却分析」(PDF)。カーネギーメロン大学。2015年3 月 14 日閲覧。
• Allan Borodinと Ran El-Yaniv (1998)。オンライン計算と競合分析。pp. 20、141。