アルゴリズムクイックリファレンス 第2版

376

■

11

章 新たな分類のアルゴリズム

実行しても異なる結果が得られるだろう。ランダムなビットストリームへのアクセ

スを仮定することで、現在の同等のアルゴリズムよりも高速なアルゴリズムが得ら

れることが多い。

実用上、決定性コンピュータではランダムなビットストリームの生成が非常に困

難なことを理解しておくべきだ。実際には真のランダムビットストリームと区別す

ることができない疑似ランダムビットストリームを生成することは可能だが、この

種のストリームを生成するコストは無視できない。

11.4.1

 集合のサイズを推定する

確率的アルゴリズムが使えることで得られる速度向上の例として、

n

個の異なる

オブジェクトの集合のサイズを推定することを仮定する。すなわち、個々の要素の

観察から

n

の値を推定したい。すべてのオブジェクトを数え上げるのが単純な方法

だろう。このコストは

O(n)

となる。明らかに、このプロセスは正確な答えを保証

する。しかし、もっと迅速に計算したく

て、

n

の値が不正確でも構わないなら、例

11-6で述べるアルゴリズムが、より高速な代替アルゴリズムとなる。このアルゴリ

ズムは、限られた区域の生物の個体数を評価するために生物学者が行う標識再捕獲

法（

mark-and-recapture experiment

）と同様である。ここでは、全集団の中のラ

ンダムな個体を返すジェネレータ関数を用いる。

例

11-6

 確率的数え上げアルゴリズムの実装

def computeK(generator):

"""

確率的数え上げアルゴリズムを用いて推定計算をする。 ...