メルド操作のならしコスト（償却原価）の定義と計算方法

メルド操作のならしコストとは

メルド（meld）操作のならしコスト（償却原価）を正確に算出することは、決して簡単な作業ではありません。最大の難しさは、ランダムな操作列の中で同じ操作でも実行される位置によって実際のコストが大きく変動する点にあります。システム設計の目標は操作列全体のコストによって左右されますが、操作のならしコストを操作列のコストだけから定義しても、有益な結果は得られません。こうした状況に対処する有効な手段となるのが、ポテンシャル関数を導入して実際のコストの変動を相殺する手法です。本稿では、このポテンシャル法に基づくならしコストの概念について解説します。

ならしコストの定義

基本操作の集合 P = {P₁, P₂, …, P_k} を持つ抽象データ型（ADT）を B とし、B を実装するデータ構造を DS とします。さらに、データ構造の各構成（configuration）に対して非負の実数値を対応付けるポテンシャル関数 F を定義します。ここで、初期構成 Φ に対しては F(Φ) = 0 が成り立つものと仮定します。

ある構成 DS に対して操作 P_k を実行したときに得られる新しい構成を DS^j と表記し、その操作を実行する際の実際のコスト（真のコスト）を C とします。

このとき、構成 DS 上で動作する操作 P_k のならしコスト a(P_k, DS) は、次の式で与えられます。

a(P_k, DS) = C + F(DS^j) − F(DS)

ならしコストの漸近評価

サイズ m のすべての構成 DS について a(P_k, DS) ≤ c・g(m) が成り立つならば、操作 P_k のならしコストは O(g(m)) であると結論づけられます。つまり、ポテンシャル関数による調整後のコストが入力サイズ m の関数 g(m) で上から抑えられる場合、その操作のならし計算量は O(g(m)) として評価できるのです。