一般的に、比較の最小数をどのように設定しますか？
質問する
13165 次
2 に答える
7
ドナルド・クヌースを引用すると（ウィキペディアでは、現時点ではTAOCPのコピーがないため）、比較数の下限は6です。
http://en.wikipedia.org/wiki/Selection_algorithm（「下限」というタイトルのセクションまでスクロールダウンします）。
あなたの目標は、事実上、kがリストの半分のサイズであるkの最小値を見つけ、切り上げて（つまり、k = 3; n = 5）、それらの最大値を取得することです。それをページの数式に接続すると、次のようになります。
(5 - 3) + 1 + 1 + 2 = 6
この場合、必要な比較の実際の最小数も6です。
中央値を見つける作業がk個の最小値を見つけるのと同じくらい難しいかどうか疑わしい場合は、5.3.3章の後のKnuthのTAoCP、ボリューム3、演習＃2を参照してください。
于 2009-10-18T19:22:28.857 に答える
4
これについては、ドナルド・クヌースのThe Art of Computer Programmingの第3巻、セクション5.3.3、最小比較の選択に多くの資料があります。ここでは、比較の最小数に関するより一般的な質問で、n個の値が考慮されます。（この値はV t（n）で表されます）。
Knuthは、V t（n）に対してn --t +（t-1）⌈lg（n + 2 --t）⌉の上限を与えます。これは、トーナメントシステムによってn --t+2の最大要素を最初に決定することによって達成されます。これを削除し（ t番目に大きいものにすることはできないため）、残りの要素の1つに置き換え、すべての要素がこの手順の一部になるまでこの手順を続けます。この段階で最大の要素は、オリジナルセット。この場合、n=5およびt=3であるため、この式で与えられる上限は6回の比較です。
Knuthは、この上限はn≤6の場合に正確であると述べているため、この場合に当てはまります。一般に、私の理解では、選択（およびソート）のための最小比較アルゴリズムを見つけるための一般的な手順はなく、nの値を増やすためのレコードは、通常、より大きな値には一般的に適用できないか、単に打ち負かされる特別なトリックを使用しますnが増加するときの他のトリック。
于 2009-10-18T20:02:42.470 に答える