A [N/4] ソートされていない配列 A の要素を選択するためのアルゴリズムを探しています。ここで、N は配列 A の要素の数です。アルゴリズムにサブリニア時間で選択を実行させたいと考えています。基本的な知識があります。 BSTなどのような構造？可能な限り高速にしたいので、実装するのが難しくないことを念頭に置いて、どのアルゴリズムが最適かを考えてください。ここで、N は 250000 まで変化する可能性があります。ユニークな要素
1 に答える
2
@Jerry Coffinが述べたように、前もって前処理を行う意思がない限り、ここで劣線形時間アルゴリズムを取得することは期待できません。この問題に線形時間アルゴリズムが必要な場合は、クイックセレクトアルゴリズムを使用できます。クイックセレクトアルゴリズムは、O（n 2）の最悪の場合に予想されるO（n）時間で実行されます。中央値の中央値アルゴリズムは、最悪の場合のO（n）の動作をしますが、一定の係数が高くなります。役立つと思われるアルゴリズムの1つは、イントロセレクトアルゴリズムです。これは、前の2つのアルゴリズムを組み合わせて、定数係数が低い最悪の場合のO（n）アルゴリズムを取得します。このアルゴリズムは通常std::nth_element、C++標準ライブラリでアルゴリズムを実装するために使用されるものです。
事前に前処理を行う場合は、すべての要素を順序統計ツリーに入れることができます。その時点から、時間O（log n）のワーストケースで任意のkのk番目の要素を検索できます。ただし、必要な前処理時間はO（n log n）であるため、クエリを繰り返し実行しない限り、これが最適なオプションとはなりません。
お役に立てれば！
于 2012-07-07T22:14:25.060 に答える