合計で1の重みのセットが与えられ、それらを次々に並べて、重みに比例した長さの一連のビンを作成したとします。各ビンに、その行の位置に対応する整数を割り当てます。
[0,1]に任意の数がある場合、この数が入るビンに対応するインデックスを確認できるようにしたいと思います。これを一定時間で行うアルゴリズムを考え出すことはできますか？
対数時間の解法は簡単ですが、もっと良いものを期待しています！
2 に答える
3
これはおそらく、時間O（1）の離散分布からランダムサンプルを生成するために使用できるエイリアスメソッドを使用して実現できます。変換を反転するだけで、このアルゴリズムを適応させて問題を解決できると思います。これにより、一様確率変数から離散バケットにマッピングする代わりに、離散バケットから一様変数にマッピングできます。そこから、値がどのバケットに分類されるかを判別できます。
お役に立てれば！
編集：私は最近、エイリアスメソッドと他の関連するトリックの広範な記事を書きました。うまくいけば、これによりアルゴリズムとその直感がより明確で簡単になります！
于 2011-09-10T22:34:50.727 に答える
0
k個のエントリを含むテーブルを作成し、1/kは最小のエントリよりも小さくする必要があります。次に、それらが指す場所へのエントリをテーブルに入力すると、O（1）が得られます。
kの制限を緩和すると、多段階ルックアップを作成できます。最初のステップは上記のとおりですが、2番目のステップは線形または対数探索です。これは、になりますO(log2(n/k))。n/k, k=n => O(log2(1)) = O(1)？
テーブル内で使用するエントリを見つけるには、floor（x * k）です。
于 2011-09-10T22:35:46.330 に答える