私は現在、中央値 alg の中央値を研究しています。
ウィキから勉強した後、質問があります: 入力サイズが 5 で割り切れない場合はどうなりますか? 中央値アルゴリズムの中央値を使用して中央値を見つける方法は?
1 に答える
2
いくつかの点で、入力の長さが 5 の倍数でない場合でも、median-of-medians アルゴリズムを続行できます。1 つのオプションは、最後のブロックに残りの要素だけを含め、その中央値を取り、前のように処理することです。もう 1 つのオプションは、要素を 5 つのブロックに分割して中央値を取るときに要素を完全に無視することです。これは、5 つ未満の要素を無視して見つかったピボットが、この方法で見つかったピボットの品質を著しく低下させないためです (つまり、最大 4 つの欠落要素を無視して、おおよそ 70/30 の分割を取得し、それらを追加しても分数が混乱することはありません)。
お役に立てれば！
于 2013-05-28T18:18:02.970 に答える