binary-search-tree - 平衡二分探索木の償却複雑度

Question

償却された複雑さが何を意味するのか完全にはわかりません。バランスのとれた二分探索木データ構造 (例: 赤黒木) を使用します。通常の検索のコストは当然 log(N) です。ここで、N はノードの数です。しかし、一連の m 回の検索を、たとえば昇順で実行した場合の償却後の複雑度はいくらになるでしょうか。log(N)/mだけですか？

Answer 1

漸近分析は、アルゴリズムの実行時間の上限を設定するための厳密な方法と見なすことができますが、償却分析はいくらか自由な方法です。

たとえば、2 つのステートメント S1 と S2 を持つアルゴリズム A を考えてみましょう。S1 の実行コストは 10 で、S2 の実行コストは 100 です。両方のステートメントは、次のようにループ内に配置されます。

n=0;
while(n<100)
{
  if(n % 10 != 0)
  {
    S1;
  }
  else
  {
    s2;
  }
  n++;
} 

ここで、S1 の実行回数は、S2 の回数の 10 倍です。しかし、漸近解析では、S2 に 10 単位の時間がかかり、100 回実行されるループ内にあるという事実のみが考慮されます。したがって、実行時間の上限は 10 * 100 = 1000 のオーダーです。一方、償却分析では、ステートメント S1 および S2 が実行される回数が平均化されます。したがって、実行の上限時間は 200 のオーダーです。したがって、償却分析により、アルゴリズムの実行上限をより正確に見積もることができます。

Answer 2

バランスの取れた検索ツリーの場合、償却された複雑さは漸近的なものに等しくなります。各検索操作にはO(logn)、漸近的にも平均的にも時間がかかります。したがって、m検索の平均複雑度は になりますO(mlogn)。

Answer 3

1回の操作の複雑さはlog(N)ですが、m個の検索操作(ルートノードからターゲットノードまで毎回)を実行する必要があるため、mlog(N)だと思います。

EDIT：@ user1377000あなたは正しいです、漸近的な複雑さから償却された複雑さを間違えました。しかし、log(N)/m ではないと思います... m 回の検索操作をすべて O(logN) 時間で完了できるとは限らないためです。

アルゴリズムの償却分析とは何ですか? これが役立つかもしれないと思います。