N 個の実数の特定の配列では、すべての数値に独自のキーがありますが、キーは必ずしも異なるとは限りません。k 個の異なる鍵があることが知られています。
k=O(log N) の場合、O(N log (log N)) の複雑さで安定した並べ替えアルゴリズムを見つける必要があります。O(N) の余分なスペースを使用できますか?
私はすべてを試しましたが、何も考えられません。
7001 次
5 に答える
3
Tilman Vogel が指摘しているように、入力データに特定の制限を課すことにより、理論的には Θ(n log(log n)) の複雑さで実行できるアルゴリズムがあります。ほとんどの実用的なアプリケーションで大きなメリットを提供する可能性は低いと思われ、おそらく実装を見たことがないのですが、それらがユースケースに適合する場合、それらのアルゴリズムのベンチマークがより高速であるかどうかを非常に知りたいと思います.
これは、Steven S. Skiena のThe Algorithm Design Manualからの抜粋で、汎用の Θ(n log(log n)) ソート アルゴリズムを考え出すことが不可能な理由を説明しています。
最悪の場合の O(n log n) 時間で実行されるいくつかの並べ替えアルゴリズムを見てきましたが、どれも線形ではありません。n 個のアイテムを並べ替えるには、確かにそれらすべてを調べる必要があるため、並べ替えアルゴリズムは最悪の場合でも Ω(n) でなければなりません。この残りの Θ(log n) ギャップを埋めることができるでしょうか?
答えはノーだ。Ω(n log n) の下限は、異なる n ごとに実行中にソート アルゴリズムが異なる動作をしなければならないことを観察することによって示すことができます! n 個のキーの順列。各ペアごとの比較の結果は、比較ベースの並べ替えアルゴリズムの実行時の動作を制御します。このようなアルゴリズムの実行可能なすべてのセットは、n! のツリーと考えることができます。葉。最小の高さのツリーは可能な限り最速のアルゴリズムに対応し、lg(n!) = Θ(n log n) となります。
于 2013-06-11T10:53:27.727 に答える
1
この境界を達成するには、木、特に二分探索木について考える必要があります。親、左の子、右の子、色など、ノードにいくつかの追加情報を持つ二分探索木のクラスが存在します...はい、赤黒の木について話しています。RB ツリーに 1 つのノードを挿入するための時間計算量は O(log n) です。n はツリーのノード数です。基本的な考え方は、配列をトラバースし、RB ツリーのすべての要素を挿入することですが、1 つの制約があり、重複した要素が検出された場合は、挿入しないでください!!!、カウントするだけです! どうやってするか？簡単です。ノードにフィールド「カウント」を追加するだけで、重複する要素が見つかるたびにカウンターを増やすだけで、新しいノードとして挿入しないでください。これを行うと、RB ツリーには O(k) 個の要素しかありません。つまり、この例では O(log n) です。したがって、RB ツリーに 1 つのノードを挿入する複雑さは O(log (log n)) です。RB ツリーにすべての要素を挿入すると、時間計算量は O(n log (log n)) になります。次のステップは、ツリーを順番にトラバースすることです!!、カウンターが存在するようにすべての要素を複製します。これを行うと、並べ替えられた配列が得られます (RB ツリーはバイナリ検索ツリーです)。順序どおりにトラバースする時間の計算量は O(n) であるため、全体の時間の計算量は O(n log (log n)) になります。
于 2015-09-08T18:10:17.103 に答える