Loading article…
コンピュータサイエンスにおいて、償却分析は、与えられたアルゴリズムの複雑さ、つまり実行にどれだけのリソース（特に時間やメモリ）が必要かを分析する方法です。償却分析の動機は、最悪の実行時間を見ることは悲観的すぎる可能性があるということです。代わりに、償却分析では、一連の操作の実行時間をそのシーケンス全体で平均します。[ 1 ] : 306結論として、「償却分析は、最悪のケース分析や平均ケース分析 などの他の手法を補完する有用なツールです。」[ 2 ] : 14 [ 3 ]
アルゴリズムの特定の操作において、特定の状況（例えば、入力パラメータ化やデータ構造の内容）によっては、リソースの大幅なコストが発生する場合もあれば、それほどコストがかからない場合もあります。償却分析では、コストのかかる操作とコストの低い操作の両方を、一連の操作全体にわたってまとめて考慮します。これには、入力の種類、入力の長さ、およびパフォーマンスに影響を与えるその他の要因を考慮することが含まれる場合があります。[ 2 ]
償却分析は、当初は集計分析と呼ばれる手法から派生したもので、現在は償却分析に包含されています。この手法は、ロバート・タージャンが1985年の論文「償却計算複雑性」 [ 1 ]で初めて正式に導入したもので、当時一般的に用いられていた確率的手法よりも有用な分析形式の必要性に対応していました。償却は当初、特に二分木や和集合演算を含む非常に特定の種類のアルゴリズムに用いられていましたが、現在では広く普及しており、他の多くのアルゴリズムの分析にも用いられています。[ 2 ]
償却分析には、どのような一連の操作が可能かを把握する必要があります。これは、操作間で状態が維持されるデータ構造において最もよく見られるケースです。基本的な考え方は、最悪の操作によって状態が変更され、最悪のケースが長期間再発しないようにすることで、そのコストを「償却」できるというものです。
償却分析を行う方法は、一般的に集計法、会計法、潜在法の3つがあります。これらはすべて正しい答えを導きます。どれを使用するかは、特定の状況に最も都合の良い方法によって決まります。[ 4 ]
JavaやC++のように、要素を追加するにつれてサイズが大きくなる動的配列を考えてみましょう。サイズが4の動的配列から始めた場合、4つの要素を追加する操作は定数時間で完了します。しかし、5番目の要素を追加するには、配列がスケーリングされたサイズの新しい配列を作成し、古い要素を新しい配列にコピーしてから新しい要素を追加する必要があるため、時間がかかります。次の数回の要素追加操作も同様に定数時間で完了しますが、その後の追加には、配列サイズのスケーリングを再度ゆっくりと行う必要があります。ArrayListstd::vector
一般に、任意の数に対して任意の初期サイズの配列へのプッシュの回数で、配列をスケーリングするステップの時間は等比数列で加算され、残りのプッシュごとに一定の時間も加算されます。したがって、プッシュ操作あたりの平均時間はこの推論は、償却分析を用いてより複雑なデータ構造に形式化および一般化することができる。[ 4 ]
以下に、キュー（FIFOデータ構造）のPythonによる実装例を示します。
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 () #出力リストから最後の要素をポップして返しますエンキュー操作は、入力配列に要素を追加するだけの操作です。この操作は入力配列の長さにも出力配列の長さにも依存しないため、定数時間で実行されます。
しかし、デキュー操作はより複雑です。出力配列に既にいくつかの要素が含まれている場合、デキューは定数時間で実行されます。そうでない場合、デキューには入力配列から出力配列にすべての要素を追加するのにかかる時間。ここでnは入力配列の現在の長さです。入力からn個の要素をコピーした後、出力配列が再び空になるまでに、それぞれ定数時間でn 回のデキュー操作を実行できます。したがって、 n 回のデキュー操作のシーケンスはわずか で実行できます。時間、つまり各デキュー操作の償却時間は . [ 5 ]
あるいは、入力配列から出力配列への任意の項目のコピーにかかるコストを、その項目の以前のエンキュー操作に課金することもできます。この課金方式では、エンキューの償却時間は2倍になりますが、デキューの償却時間は短縮されます。 .
[償却分析]は、一般的に平均ケース分析と呼ばれるものとは異なります。償却分析はデータ値の分布について何の仮定も行わないのに対し、平均ケース分析はデータが「悪い」ものではないと仮定するからです（例えば、一部のソートアルゴリズムは、すべての入力順序に対して「平均的に」はうまく機能しますが、特定の入力順序では非常に悪い結果になります）。つまり、償却分析は最悪ケース分析ですが、個々の操作ではなく、一連の操作に対して行われます。
