償却解析

コンピュータサイエンスにおける 償却解析 (しょうきゃくかいせき、英語: Amortized_analysis、ならし解析ともよばれる)とは、与えられたアルゴリズムの時間計算量または、コンピュータプログラムの文脈における資源、特に時間またはメモリをどれだけ必要とするかを分析する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。 与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、そのパフォーマンスに影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。

歴史

償却解析は、当初、aggregate analysis(集計分析)とよばれる手法から出現した。これは現在では償却解析に包含されている。この技術は最初、Robert Tarjanの 1985 年の論文 Amortized Computational Complexity で公式に導入され、これまで使用されてきた共通の確率的手法よりもより強力な分析形態の必要性を主張した。償却は最初非常に明確な種類のアルゴリズム、とりわけ二分木や union 操作( SQL の union を意味しており、共用体のことではないと思われる。)に使用された。しかし、いまや至る所にあり、多くのほかのアルゴリズムの分析時にも活動する。

手法

この手法は、どの一連の操作が可能かどうかの知識を必要とする。これは、データ構造の場合には最も一般的である。それは、操作間に固執する状態を持つ。基本的な考え方は、最悪な場合の操作は、そのケースが長期間にわたって再び起こらないように状態を変えることができ、そのコストを"償却する"ということである。 一般に、償却解析を行う 3 つの方法がある。これらはすべて同一の結果を与え、使用法の相違は主に状況および個人の好みである。

• Aggregate analysis - これは、 一連の n 回の操作の全コストに関する上限 T(n) を決定し、 償却コストを T(n) / n と計算する。
• en:Accounting_method - これは、各操作の各コストを決定し、その即時の実行時間および将来の操作の実行時間への影響を結合する。たいてい、多くの短期実行操作(short-running operations)は少しずつ好ましくない状態の"負債"を蓄積し、一方でレアな長期実行操作(long-running operations)はそれを劇的に減少させる。
• en:Potential_method - これは、accounting method と似ているが、後で課金を補償するために、早期に操作に課金する。

例

動的配列

Java における ArrayList のような、より多くの要素が追加されるようなサイズで大きくなる動的配列を考える。サイズ 4 の動的配列で始めた場合、それに 4 つの要素を push するのに定数時間かかるだろう。しかし、それに 5 つ目の要素を push することは、現在のサイズの 2 倍 (8) の新しい配列を作成し、古い要素を新しい配列にコピーし、さらに新しい要素を追加するので、より長い時間がかかるだろう。次の 3 つの push 操作は、同様に定数時間かかる。そして次の追加は配列サイズの遅い 2 倍化を必要とするだろう。 一般に、サイズ n の配列に n + 1 回の push を行うことを考えたとき、最後の 1 回以外は定数時間かかり、最後の 1 回はサイズの 2 倍化を行うのに O(n) かかることに気づく。全部で n + 1 回の操作があったので、これの平均を取り、動的配列への要素の push が $O({\tfrac {n+1}{n}})=O(1)$ の定数時間かかることがわかる。

キュー

Ruby の キュー(FIFO)実装を見てみよう。

class Queue
  def initialize
    @input = []
    @output = []
  end

  def enqueue(element)
    @input << element
  end

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop
      end
    end

    @output.pop
  end
end

enqueue 操作では、単に入力配列に要素を push している。この操作は入力または出力の長さに依存せず、それゆえ定数時間で走る。 しかし、dequeue 操作はより複雑である。もし出力配列がすでになんらかの要素を持っていれば、それは定数時間で走る。そうでなければ、dequeue は入力配列から出力配列にすべての要素を追加するのに O(n) かかる。ここで、 n は入力配列の現在の長さである。入力から n 要素をコピーした後で、我々は出力配列が再び空になる前に n 回の dequeue 操作を行うことができる。その操作のそれぞれは定数時間かかる。このようにして、我々はわずか O(n) の時間で一連の n 回の dequeue 操作を行うことができる。これは、それぞれの dequeue 操作の償却された時間が O(1) であることを意味する。 あるいは、我々はそのアイテムに対する初期の enqueue 操作に対する、入力配列から出力配列への各アイテムのコピーのコストを請求することができる。この請求スキームは enqueue に対する償却時間を 2 倍にするが、dequeue に対する償却時間を O(1) に減少させる。

一般的な使用

• 一般的な使用法として、"償却アルゴリズム" は償却解析がよりよく行われることを示したものである。
• オンラインアルゴリズム は共通して償却解析を使用している。

参考文献

• Allan Borodin and Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 20,141. http://www.cs.technion.ac.il/~rani/book.html