9

n 要素のマルチセット A (ソートされていない) が与えられた場合、A に多数要素 (つまり、A に n/2 回以上出現する要素) が含まれているかどうかを判断するための O(n) 時間アルゴリズムが必要であるとします。これを O(n) 時間で簡単に解決するには、線形時間選択アルゴリズムを使用して中央値 (x と呼びます) を見つけ、A で x が何回発生するかを数え、カウントが n/2 を超える場合は過半数として返します。 （それ以外の場合、答えは「過半数はありません」です）。ここで、問題の次の一般化を考えてみましょう: A と整数 k < n が与えられた場合、A に n/k 回以上出現する値が含まれているかどうかを判断するアルゴリズムが必要です (そのような値が多数存在する場合、それで十分です)。それらの1つを見つけるために）。これを行うアルゴリズムを設計し、その複雑さを n と k の関数として分析します。この質問に対するあなたの評価は、あなたのアルゴリズムがどれだけ速いかによって決まります (もちろん、それも正しい必要があります)。O(kn) 時間のアルゴリズムには 10 ポイントの部分的な評価点が与えられ、O(n log k) 時間のアルゴリズムには完全な評価点が与えられます。

今、私は問題に対して2つの解決策を考え出しましたが、どちらもO(n log k)の要件を完全には満たしていません。すぐに、O（n log n）アルゴリズムを使用して配列をソートできることがわかりました。次に、要素がn / k回以上線形に繰り返されるかどうかを確認しますが、それはO（n log n）であり、O（n log k）ではありません

また、入力と同じデータ型の配列と k の長さの int を作成することによって行われる O(nk) メソッドを見つけて、ある程度理解しました。次に、各要素を空の要素に入れ、そのカウンターをインクリメントするか、その中の 1 つの要素と一致する場合は、k + 1 番目の一意の要素に到達するまでカウンターをインクリメントし、その時点で 0 に達するまですべてのカウンターを 1 減らします。空と見なされ、新しい要素をその中に配置できます。入力配列の最後まで続きます。次に、完了後に残ったすべての要素をチェックして、それらが n/k 回以上発生するかどうかを確認します。ただし、これには n 個の元の要素を k 個の新しい配列要素すべてに対してチェックする必要があるため、O(nk) になります。O(n log k) でこの問題を解決する方法に関するヒントはありますか? O(nk) アルゴリズムは、彼が私たちに考えさせたい方法に沿っていると思いますが、私は'

4

3 に答える 3

7

説明した方法は、再帰的に使用する必要があります。

これを思い出すとselect、中央値以下の要素が中央値の左側に移動します。

Aサイズの場合n。

の中央値を見つけますA。n/2次に、中央値で分割された長さの2つのサブマルチセットのそれぞれの中央値を見つけます。n/4中央値で分割された長さの4つのサブマルチセットのそれぞれの中央値を見つけます。葉の長さが長くなるまで再帰的に続けn/kます。これで、再帰ツリーの高さはですO(lgk)。再帰ツリーの各レベルには、O(n)操作があります。少なくとも複数n/k回繰り返される値が存在する場合、その値はサブマルチセットkの長さでこれらのいずれかになります。n/k最後の操作もで行われO(n)ます。したがって、要求された実行時間は。になりO(nlgk)ます。

于 2012-08-24T22:04:05.840 に答える
2

O(kn) アルゴリズム

おそらく、O(kn) アルゴリズムは次のようなものになるのではないでしょうか。

  1. 等間隔の k 個の要素を見つけます (中央値と同様の線形選択アルゴリズムを使用)
  2. これらのそれぞれについて、一致した数を数えます

要素が n/k 回出現する場合、それはこれらのいずれかでなければならないという考えです。

O(nlogk) アルゴリズム

おそらく、質問で提案されたスキームをツリー構造と一緒に使用して、k 要素を保持できます。これは、全体の O(nlogk) に対して、一致の検索が k ではなく log(k) のみになることを意味します

最初のパス (考慮する必要がある k 個の候補を見つける) と、各要素の正確な数を計算する 2 番目のパスの両方にツリーを使用する必要があることに注意してください。

また、カウンターをデクリメントするために遅延評価スキームを使用したい場合があることに注意してください (つまり、デクリメントする必要があるサブツリー全体をマークし、そのパスが次に使用されるときにのみデクリメントを伝播します)。

O(n) アルゴリズム

実際にこれに遭遇した場合は、ハッシュベースの辞書を使用してヒストグラムを保存することを検討します。これにより、迅速な解決策が得られるはずです。

たとえば、Python では、これを (平均して) O(n) 時間で解決できます。

from collections import Counter
A=[4,2,7,4,6]
k=3

element,count = Counter(A).most_common()[0]

if count>=len(A)//k:
    print element
else:
    print "there is no majority"
于 2012-08-24T21:49:57.120 に答える
0

あなたがこれを見たかどうかはわかりませんが、アイデアを得るのに役立つかもしれません:

配列 L に多数決要素があることがわかっているとします。

要素を見つける 1 つの方法は次のとおりです。

Def FindMajorityElement(L):

    Count = 0

    Foreach X in L

        If Count == 0
            Y = X

        If X == Y
            Count = Count + 1
        Else
            Count = Count - 1

    Return Y

O(n) 時間、O(1) 空間

于 2012-08-24T22:09:44.690 に答える