4

線形時間アルゴリズムを設計および解析して、n 個の要素のリストに、リスト内で少なくとも n/10 回繰り返される要素が存在するかどうかを判断します。

これどうやってするの？私は自分の考えを答えとして投稿しています。

4

3 に答える 3

12

要素は同等だと思います。

n/10 番目、2n/10 番目、...、9n/10 番目、10(n/10) 番目に小さい要素1の選択アルゴリズムを実行します。

これらはあなたの候補です。それぞれの #occurrences を確認し、そのうちの 1 つが少なくとも n/10 回繰り返される場合、答えはtrueです。それ以外の場合は ですfalse。

証明:
要素が少なくとも n/10 回出現する場合、(ソートされたリストで) 2 と「交差」する必要k*n/10がkあります。したがって、この要素は「候補」として選択され、後で正確に何回出現するかを (数えることによって) 発見し、 を返しtrueます。

要素が何n/10回も繰り返されない場合、アルゴリズムはfalse各候補をチェックする最後のステップで自明に戻ります。

複雑さ:
各選択アルゴリズムはO(n)であり、10 回実行されます。また、候補ごとにリストの線形スキャンが必要であり、これも全体的にO(n)合計されO(n)ますが、定数はひどいものです。

説明:

(1) 選択アルゴリズムは、ソートされたリストのインデックス n/10、2n/10、...9n/10 にある要素を見つけ、アルゴリズム自体はO(n)

[1,2,..,100,100,..,100](2) (11 かける 100)の例を見てみましょう。
リストがソートされ、要素 100 がlist[9*n/10](index 9*n/10) に表示されることに注意してください。選択アルゴリズムの考え方は、リストをシャッフルしても、select(list,9*n/10)常に同じ要素 (この場合は 100) を返すという9n/10ものです。これは、並べ替えられたリストの 4 番目の要素であるためです (これがアルゴリズムの動作です)。

eここで、繰り返しの各要素 ( とします) について、並べ替えられたバージョンのリストでは、インデックス内のすべての要素が になるようなn/10インデックスがあることがわかります。これらのインデックスの1 つは、一部のインデックスの 1 つである必要があります(理由を自分で納得させてください!)。したがって、上の選択アルゴリズムはを生成します。ii,i+1,...,i+n/10ek*n/10kk*n/10e

于 2012-11-24T15:59:01.087 に答える
3

大部分の要素 (頻度が n/2 よりも高い要素) を見つけるための巧妙なシングル パス アルゴリズムを教えてください。

best = null
count = 0

foreach x in list:
   if (count == 0)
      count++
      best = x
   else if (best == x)
      count++
   else
      count--

return best

多数要素がある場合、上記のアルゴリズムはそれを見つけます (1 回のパス、一定のスペース)。それがどのように機能するかを理解すると、n/10 のケースにどのように適応できるかがわかります。

于 2012-11-24T16:51:30.673 に答える
0

私の解決策は、リストを 10/n グループに分割し、各グループに 10 個の要素を含め、各グループでランダム選択ソートを実行することです。これには O(1)*O(n) 時間、つまり O(n ）。

要件を満たすには、候補要素が n/10 グループのそれぞれに表示される必要があるため、最初のグループの 10 個の要素のそれぞれに対してスキャンを実行できます。これには 10*O(n) の時間がかかります。

したがって、アルゴリズムの全体の時間は O(n)+10*O(n) であり、それでも O(n) です。

ただし、グループ内の要素が次のような場合、これは機能しません。

1,2,3,4,5,6,7,8,9,10
11,11,11,11,11,11,11,11,11,11
...
11,11,11,11,11,11,11,11,11,11

私のアルゴリズムは、そのような要素が存在しないことを返しますが、実際に11は n/10 回以上出現する要素です。

于 2012-11-24T15:52:53.783 に答える