償却解析のソースを表示

{{翻訳直後|1=[https://en.wikipedia.org/w/index.php?title=Amortized_analysis&oldid=754316633 en:Amortized analysis 00:30, 12 December 2016 (UTC)]|date=2017年5月}}
<!-- {{confusing|date=January 2014}} -->

[[計算機科学]]における '''償却解析'''（しょうきゃくかいせき、{{lang-en-short|amortized analysis}}）または'''ならし解析'''とは、与えられた[[アルゴリズム]]の[[計算複雑性理論|複雑性]]あるいは計算機資源（特に時間またはメモリ）をどれだけ必要とするかを[[アルゴリズム解析|分析]]する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。<ref name=CMU>{{cite web2|title=Lecture 7: Amortized Analysis|url=https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0206.pdf|website=www.cs.cmu.edu|accessdate=14 March 2015}}</ref>
与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、その性能に影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。<ref name="fiebrink">{{Citation |url=http://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf |title=Amortized Analysis Explained |first=Rebecca |last=Fiebrink |year=2007 |accessdate=2011-05-03}}</ref>

== 歴史 ==
{{Expand section|date=May 2017}}
償却解析は、当初、aggregate analysis(集計分析)とよばれる手法から出現した。これは現在では償却解析に包含されている。この技術は最初、[[ロバート・タージャン|Robert Tarjan]]の 1985 年の論文 ''Amortized Computational Complexity'' で公式に導入され、これまで使用されてきた共通の確率的手法よりもより強力な分析形態の必要性を主張した。償却は最初非常に明確な種類のアルゴリズム、とりわけ[[二分木]]や union 操作( SQL の union を意味しており、[[共用体]]のことではないと思われる。)に使用された。しかし、いまや至る所にあり、多くのほかのアルゴリズムの分析時にも活動する。<ref name="fiebrink"/>

== 手法 ==
{{Expand section|date=February 2011}}
この手法は、どの一連の操作が可能かどうかの知識を必要とする。これは、[[データ構造]]の場合には最も一般的である。それは、操作間に固執する[[:en:State_(computer_science)|状態]]を持つ。基本的な考え方は、最悪な場合の操作は、そのケースが長期間にわたって再び起こらないように状態を変えることができ、そのコストを"償却する"ということである。
一般に、償却解析を行う 3 つの方法がある。これらはすべて同一の結果を与え、使用法の相違は主に状況および個人の好みである。<ref name="Lecture 20">{{cite web|title=Lecture 20: Amortized Analysis|url=http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm|website=http://www.cs.cornell.edu/|publisher=Cornell University|accessdate=14 March 2015}}</ref>

* Aggregate analysis - これは、 一連の ''n'' 回の操作の全コストに関する上限 ''T''(''n'') を決定し、 償却コストを ''T''(''n'') / ''n'' と計算する。<ref name="Lecture 20"/>
* [[:en:Accounting_method]] - これは、各操作の各コストを決定し、その即時の実行時間および将来の操作の実行時間への影響を結合する。たいてい、多くの短期実行操作(short-running operations)は少しずつ好ましくない状態の"負債"を蓄積し、一方でレアな長期実行操作(long-running operations)はそれを劇的に減少させる。<ref name="Lecture 20">{{cite web|title=Lecture 20: Amortized Analysis|url=http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm|website=http://www.cs.cornell.edu/|publisher=Cornell University|accessdate=14 March 2015}}</ref>
* [[: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 が <math>O(\tfrac{n+1}{n}) = O(1)</math> の定数時間かかることがわかる。<ref name="Lecture 20" />

=== キュー ===
Ruby の [[キュー (コンピュータ)|キュー]]([[FIFO]])実装を見てみよう。
<syntaxhighlight lang="ruby">
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
</syntaxhighlight>

enqueue 操作では、単に入力配列に要素を push している。この操作は入力または出力の長さに依存せず、それゆえ定数時間で走る。
しかし、dequeue 操作はより複雑である。もし出力配列がすでになんらかの要素を持っていれば、それは定数時間で走る。そうでなければ、dequeue は入力配列から出力配列にすべての要素を追加するのに ''O(n)'' かかる。ここで、 ''n'' は入力配列の現在の長さである。入力から ''n'' 要素をコピーした後で、我々は出力配列が再び空になる前に ''n'' 回の dequeue 操作を行うことができる。その操作のそれぞれは定数時間かかる。このようにして、我々はわずか ''O(n)'' の時間で一連の ''n'' 回の dequeue 操作を行うことができる。これは、それぞれの dequeue 操作の償却された時間が ''O(1)'' であることを意味する。<ref name=Grossman>{{cite web|last1=Grossman|first1=Dan|title=CSE332: Data Abstractions|url=http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture21.pdf|website=cs.washington.edu|accessdate=14 March 2015}}</ref>
あるいは、我々はそのアイテムに対する初期の enqueue 操作に対する、入力配列から出力配列への各アイテムのコピーのコストを請求することができる。この請求スキームは enqueue に対する償却時間を 2 倍にするが、dequeue に対する償却時間を ''O(1)'' に減少させる。

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

== 出典 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
* {{cite book
 | first=Allan
 | last=Borodin
 | first2=Ran
 | last2=El-Yaniv
 | url=http://www.cs.technion.ac.il/~rani/book.html
 | title=Online Computation and Competitive Analysis
 | isbn=0-521-56392-5
 | publisher=Cambridge University Press
 | date=1998
 | pages=20, 141
}}

{{デフォルトソート:しようきやくかいせき}}
[[Category:償却データ構造|*]]
[[Category:アルゴリズム解析]]