ardendertatmedian-of-mediansのアルゴリズムを使用して、配列内でk番目に高い要素を見つける方法に関する記事を読んでいました。複雑さを説明する部分では、作成者は1つの要素、つまり各パーティションのを再帰的に見つけるコストを割り引いたようです。確かに、最初のピボットですべてのサブアレイを分割することはできませんよね？それで、これは複雑さを増しませんか？median-of-medians
1868 次
2 に答える
2
中央値の中央値アルゴリズムはクイックセレクトアルゴリズム用に開発されました。これはクイックソートに非常に似ていますが、パーティションの片側でのみ繰り返されるため、実際にはO（n log n）ではなく線形です。選択の問題は、集合Sの中でk番目に大きい要素を選択することです。中央値を見つけることは、k =（| S | + 1）/2の特殊なケースです。
アルゴリズムは単純です。
ピボット値を選択します。
要素を2つのセットに分割します：S <（すべての要素<p）とS≥（すべての要素≥p）。
再帰：S <が少なくともkの場合、S<でk番目に大きい要素を見つけます。それ以外の場合は、 S≥で（k-| S < |）番目に大きい要素を見つけます。
クイックソートと同様に、重要なのはピボット値を見つけることです。次のようにします。
Sの5つの要素の各グループの中央値で構成されるS中央値を作成します。
selectを再帰的に呼び出して、S中央値の正確な中央値を見つけます。
さて、|S中央値| 正確に0.2*|S|です。さらに、ピボットを取得すると、max（| S < |、| S≥）≤0.7* |S|であることがわかります。[fn 1]したがって、選択する2つの再帰呼び出しの合計は最大0.9 * |S|になります。
これで、 selectを計算する時間がΣ0.9inに比例することを示すことができます。これは明らかにnで線形です。
それがあなたにとって十分に明快だったことを願っています。
明らかでない場合は、S中央値の中央値の半分が少なくともpである必要があり（pは中央値であるため）、これらの中央値に対応する5つのグループごとに、5つの要素のうち3つ（中央値と2つ）より大きな要素）は少なくともpでなければなりません。つまり、Sの全要素の50％の60％、つまり30％になります。同様の議論は、「少なくとも」を「最大」に置き換えることにも当てはまります。したがって、2つのサブセットのうち小さい方がSのサイズの少なくとも30％であり、その結果、大きい方が最大でサイズの70％であることがわかります。
于 2012-09-22T21:49:01.097 に答える
1
p配列を分割した後の中央値の中央値の位置は、0.3*nとの間0.7*nです。
したがって、1ラウンド後、3つの可能性があります。
p == n-k、運が良ければ、最初のピボットはkO（n）にある-番目に大きい要素です（中央値の中央値と分割は両方ともO（n）です）。p > n-kの場合、k-番目に大きい要素は最初のピボットよりも小さくk - (n-p)、最初の部分の-番目に大きい要素を見つける必要があります。これには多くの要素が含まれているため、 -番目に大きい要素0.7*nを見つけるための総コストは次のようになります。kT(n) <= T(0.7*n) + C*np < n-kk、次に、2番目の部分（ピボットの後）の-番目に大きい要素を見つける必要があります。その部分も最大で0.7*n要素が大きいので、再び見積もりがあります。T(n) <= T(0.7*n) + C*n
繰り返しますが、
T(n) <= T((0.7)^k * n) + C*(1 + 0.7 + ... + (0.7)^(k-1))*n
<= T(1) + C/(1 - 0.7)*n
これは明らかにO（n）です。
于 2012-09-22T19:59:08.680 に答える