償却分析の概要
1. 概要
この記事では、一連の操作の実行時コストを見積もる手法として、償却分析を紹介します。 償却原価を評価するための2つの一般的なアプローチ、つまり集計方法と会計方法を順を追って説明します。
2. 償却分析
優れたアルゴリズムの設計には、多くの場合、データ構造の使用が含まれます。 データ構造を使用する場合、通常、操作は個別にではなくシーケンスで実行されます。
このようなシーケンスの複雑さを分析する場合、1つの簡単なアプローチは、そのシーケンス内の個々の操作の実行時間の上限を決定することです。 これらの値を合計すると、シーケンス全体の実行時間の上限を達成できます。
一部のタイプのデータ構造では、このアプローチで十分な場合があります。 ただし、多くの場合、同じ操作でシーケンス全体で非常に異なるコストが発生します。 具体的には、まれに最悪の場合のコストしか発生しない場合があります。
このような場合、個々の操作の最悪の場合のコストを単純に合計すると、実際の実行時コストを大幅に過大評価する可能性があります。
償却分析は、シーケンス全体でより「高価な」操作のコストを平均化することにより、この問題を解決しようとします。より正式には、償却分析は、シーケンス内の各操作の平均コストを検出します。シーケンスは最悪の場合を経験します。このようにして、シーケンスの最悪の場合のコストのより正確な限界を見積もることができます。
例を使ってこのアイデアを動機付けましょう–動的配列。
3. 動的配列
空で始まり、長さが N = 1、要素数が n =0の配列Aについて考えてみます。 配列の最後に要素を追加できますが、配列がいっぱいになると、自動的にさらにスペースを割り当てる必要があります。
したがって、数回挿入すると、配列は次のようになります。
このタイプのデータ構造は、動的配列と呼ばれます。
3.1. 追加操作
動的配列の最後に要素xを追加するには、 append （ x ）という操作を呼び出します。
append （ x ）には2つのステップがあります。
- xをアレイ内の次に使用可能な位置に割り当てます
- アレイがいっぱいになっているかどうかを確認します。 そうである場合は、関数 copy（）を呼び出して、さらにスペースを割り当てます。
copy（）は、前の配列の各要素を2倍の長さの新しい配列にコピーすることで機能します。
この操作を例を挙げて視覚化してみましょう。 上から配列Aに要素「2」を追加するとします。 append （2）を呼び出すと、次のプロセスがトリガーされます。
3.2. 一連の追加
一連のappend操作のワーストケースのコストを分析する場合は、操作の数 n に対する、追加の個々のワーストケースのコストを単純に合計できます。 。 これにより、の限界が得られます。これは、パフォーマンスのスケーリングが非常に悪いことを示しています。
ただし、この見積もりは過度に悲観的です。
このように考えると、シーケンス内のすべての append 操作で、 copy 関数を呼び出すことができると想定していますが、これは不可能であることがわかっています。 a ppend は、配列がいっぱいになったときにのみcopyを呼び出します。
代わりに、シーケンス全体の最悪のケースを特定し、このシーケンス全体の各操作の平均コストを見つけます。
償却操作コストと呼ばれるこの測定値は、append操作が実際にどれだけうまく機能するかをより正確に示します。
前に約束したように、2つの方法を見てみましょう。
- 集計方法
- 会計方法
4. 集計方法
この方法では、合計と除算のアプローチを適用します。ここで、次のようにします。
- 一連の操作全体の最悪の場合のコストを決定します。T（ n ）
- このコストをシーケンス内の操作数nで割ります。
言い換えると：
このメソッドを動的配列に適用してみましょう。
4.1. 動的配列
まず、シーケンス内の各操作のコストを決定する必要があります。 Ci を使用して、 i 番目の操作のコストを示し、単純な割り当てには1単位の時間がかかると主張します。
シーケンスの開始時にCiを手動で観察することから始めることができます：
ここでかなり明確なパターンが現れ始めています。copy（）は、iが2の因数である場合、つまりi = 1、2、4、8、16、…の場合に呼び出されます。 i copy の時間単位に加えて、単純な割り当ての1単位。
シーケンス内の他のすべての位置で、appendは1単位の時間かかります。
したがって、Ciを次のように定義できます。
ここで、 T （ n ）を計算するために、個々の操作コストCiを次の順序で単純に合計します。
これで、最後の2つの合計を単純化して n に等しくすることができます。これは、それらが一緒になって正確にn回発生するためです。
最後に、iはシーケンス内で最大log2 n 回の2の累乗になる可能性があることを認識することにより、最初の合計を解くことができます。 したがって、この合計を変換して、0からlog 2 n までの範囲で反復し、値2を追加する新しいインデックスjを作成できます。 j。 この手順が少しわかりにくい場合は、このページで詳細な手順を確認してください。
最後に、操作の数 n で割ると、次のようになります。
4.2. 制限事項
ご覧のとおり、この方法は非常に簡単です。 ただし、シーケンスのコストを具体的に定義した場合にのみ機能します。
また、シーケンスに複数のタイプの操作が含まれている場合、それらはすべて同じように扱われます。シーケンス内の異なるタイプの操作に対して異なる償却原価を取得することはできません。 これは理想的ではないかもしれません！
次に、いくつかのより興味深い結果をもたらすことができる会計方法を見ていきます…
5. 会計方法
この方法では、償却原価を各事業に割り当てる「料金」と考えています。
オペレーションに遭遇するたびに、この「料金」を使用して支払いを試みます。
オペレーションの費用が実際に「料金」よりも低い場合は、銀行口座に変更を隠しておきます。 運営に実際に「料金」よりも高い費用がかかる場合は、銀行口座に請求して費用を賄うことができます。
アイデアは、後で遭遇する可能性のある「高価な」操作に支払うために、「安い」操作中に十分なお金を節約したいということです。
動的配列に対してこのメソッドをステップスルーしてみましょう。
5.1. 動的配列
この分析では、$1を使用してランタイムの1単位を表します。 これは、安価な追加の費用が1ドル、高価な追加の費用が$（ i +1）であることを意味します。ここで、iはシーケンス内のこの操作の位置。
では、 append 操作ごとにいくら課金する必要がありますか？
これはトリッキーな部分です。請求額が少なすぎないようにする必要があります。そうしないと、高額な業務の費用を負担しようとして破産します。 ただし、シーケンス全体の支払いに必要なコストを過大評価するため、あまり課金したくありません。
5.2. 料金の決定
このプロセスには、少し抽象的な考えが必要です。 プロセスに慣れてきましたが、役立つアプローチの1つは、単純な試行錯誤です。
それでは、1ドルの請求を試すことから始めましょう。 この例では、 B を使用して銀行の残高を示し、ΔBを使用して操作によってBに加えられた変更を示します。
明らかに、この料金は十分ではありません。 $ 1は、安価な append のコストをカバーするだけで、高価な操作の費用を節約することはできません。
$ 2を請求するのはどうですか？
2ドルの請求でも十分ではないことがすぐにわかります。
$ 3はどうですか？
これは有望に見えます！ これまでのところ、私たちの銀行口座は赤字になっていない。 そして、結局のところ、3ドルを請求することで、私たちのシーケンスの将来のすべてのコストを確実にカバーすることができます。
この主張は、単純な誘導によって証明できます。
5.3. チャージホールドの証明
最初に、最初のコピーを検討します。これは、位置 i = 0で発生し、コストは$2です。 明らかに、私たちの料金はこの費用をカバーします。
次に、帰納的なケースでは、高価なappendの直後の銀行残高が>=0であると仮定します。 これで配列は半分空になります。つまり、別の高価な append が発生する前に、 N /2-1安いappendsに遭遇する必要があります。
これらの各操作で銀行口座に$2が節約される場合、少なくとも$（ N -2）が節約されます。 $ 3の料金に加えて、これは$（ N + 1）の費用がかかる次の高価な操作の支払いに十分です。 したがって、私たちの銀行口座は赤字になりません。
したがって、3ドルの料金は、シーケンス内の将来のすべてのコストをカバーします。
これは、償却された運用コストの上限が3=であることを意味します。
5.4. さまざまな操作タイプ
今日は、1つのタイプの操作のみでシーケンスに分析を集中させました。 この場合、集計方法と会計方法の両方で、append操作の償却原価が3=O（1）であることが明らかになりました。
ただし、代わりに複数のタイプの操作でシーケンスを分析した場合、結果はそれほど一貫していない可能性があります。
集計方法は常にすべての操作を同じように扱い、シーケンス内の複数のタイプの操作について異なる償却原価を推定することはできません。
一方、会計方法は、複数の操作タイプに簡単に適用して、各の償却原価を見積もることができます。 この目標を達成するために、各操作タイプに異なる料金を割り当てるだけで、固有の償却原価を明らかにすることができます。
6. 結論
この記事では、償却原価分析の概念を紹介しました。 個々の操作に高額な最悪の場合のコストがかかる場合でも、償却分析が一連の操作が実際に非常に効率的であることを証明するのにどのように役立つかを調査しました。
