Loading article…
コンピュータサイエンスにおけるアルゴリズムの分析の分野において、会計法は会計に基づく償却分析の手法です。会計法は、集計分析や潜在的方法よりも、操作の償却コストをより直感的に説明することがよくあります。ただし、これは、このような分析がすぐに明らかになることを保証するものではありません。多くの場合、会計法の正しいパラメータを選択するには、他の 2 つの方法と同じくらい、問題と証明しようとしている複雑さの境界に関する知識が必要です。
会計法は、時間に対するO (1) の限界を証明するのに最も自然に適しています。ここで説明する方法は、そのような限界を証明するためのものです。
方法
アルゴリズムで使用される基本操作のセットが選択され、そのコストは任意に 1 に設定されます。これらの操作のコストが実際には異なる可能性があるという事実は、原理的には問題になりません。重要なのは、各基本操作のコストが一定であることです。
各集計操作には「支払い」が割り当てられます。支払いは、この特定の操作を完了するために必要な基本操作のコストをカバーすることを目的としており、残りの支払いの一部は後で使用するためにプールに入れられます。
償却分析を必要とする問題の難しさは、一般に、一部の操作に一定以上のコストが必要になることです。つまり、一定の支払いだけでは、操作自体の最悪のコストをカバーするのに十分ではありません。ただし、支払いを適切に選択すれば、これはもはや困難ではありません。コストのかかる操作は、そのコストをカバーするのに十分な支払いがプールにある場合にのみ発生します。
例
いくつかの例を挙げて、会計方法の使用方法を説明します。
テーブル拡張
必要なスペースの量がわかる前にテーブルを作成する必要があることがよくあります。 1 つの戦略として、テーブルがいっぱいになったときにテーブルのサイズを 2 倍にすることが考えられます。 ここでは、会計方法を使用して、このようなテーブルへの挿入操作の償却コストがO (1) であることを示します。
手順を詳しく見る前に、いくつかの定義が必要です。T をテーブル、E を挿入する要素、 num(T) をT内の要素数、 size(T) をTの割り当てサイズとします。ここでは、サイズn (現時点では空であると想定) の空のテーブルを作成する create_table(n) 操作と、すでにスペースが割り当てられているテーブルTに要素E をコスト 1 で 挿入する elementary_insert(T,E) 操作が存在すると想定します。
次の疑似コードは、テーブル挿入手順を示しています。
num(T) = size(T)の場合、関数table_insert(T, E)
U := create_table(2 × サイズ(T))
Tの各Fについて
基本的な挿入(U, F)
T := u
基本的な挿入(T, E)
償却分析を行わない場合、n 挿入操作に対して示せる最良の境界は O(n) です。これは、num(T) の基本挿入を実行する 4 行目のループによるものです。
会計方法を使用した分析では、テーブル挿入ごとに 3 の支払いを割り当てます。その理由は現時点では明らかではありませんが、分析の過程で明らかになります。
最初はテーブルが空で、size(T) = m であると仮定します。したがって、最初の m 回の挿入では再割り当ては必要なく、コストは 1 のみです (基本挿入の場合)。したがって、num(T) = m の場合、プールには (3 - 1)×m = 2m があります。
要素 m + 1 を挿入するには、テーブルの再割り当てが必要です。3 行目での新しいテーブルの作成は無料です (今のところ)。4 行目のループでは、m 回の基本挿入が必要で、コストは m です。最後の行での挿入を含めると、この操作の合計コストは m + 1 です。この操作の後、プールは 2m + 3 - (m + 1) = m + 2 になります。
次に、テーブルに別の m - 1 個の要素を追加します。この時点で、プールは m + 2 + 2×(m - 1) = 3m になります。追加の要素 (つまり、要素 2m + 1) を挿入すると、コストが 2m + 1、支払いが 3 になることがわかります。この操作の後、プールは 3m + 3 - (2m + 1) = m + 2 になります。これは、要素 m + 1 を挿入した後と同じ量であることに注意してください。実際、これは任意の数の再割り当てで当てはまることがわかります。
これで、挿入の支払いが 3 である理由が明らかになりました。要素の最初の挿入に対して 1 が支払われ、次にテーブルが拡張されるときに要素を移動するために 1 が支払われ、次にテーブルが拡張されるときに古い要素を移動するために 1 が支払われます。直感的に、これは、テーブルが何回拡張されても要素の貢献が「尽きる」ことがない理由を説明しています。テーブルは常に 2 倍になるため、最も新しい半分が常に最も古い半分を移動するコストをカバーします。
当初、テーブルの作成は無料であると想定していました。実際には、サイズ n のテーブルの作成には O(n) ほどのコストがかかる可能性があります。サイズ n のテーブルを作成するコストが n であるとします。この新しいコストは問題を引き起こしますか? 実際にはそうではありません。償却 O(1) 境界を示すために同じ方法を使用していることがわかりました。必要なのは支払いを変更することだけです。
新しいテーブルが作成されると、m 個のエントリを持つ古いテーブルが存在します。新しいテーブルのサイズは 2m になります。現在テーブルにあるエントリがプールに追加され、新しいテーブルの作成に必要な金額が支払われている限り、問題ありません。
最初のエントリが新しいテーブルの支払いに役立つとは期待できません。それらのエントリは、現在のテーブルの支払いをすでに済ませています。そのため、コストの支払いには最後のエントリに頼る必要があります。つまり、エントリごとに支払いを追加する必要があるため、合計支払いは 3 + 4 = 7 になります。
参考文献
- Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第2版。MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7 。セクション17.2：会計方法、pp. 410–412。