algorithm - median-of-medians アルゴリズムの定数 5 はどこから来ますか?

Question

Median of Medians アルゴリズムで「5」がどこから来たのかを理解しようとしてきましたが、それがどのように導き出され、なぜ最適なのかについての簡単な説明が見つからないようです。

たとえば、なぜ 7 と言うのが実行可能なオプションではないのでしょうか?

5 の唯一の利点は、中央の両側に 2 つのアイテムがあり、5 つのアイテムの並べ替えが 3 つ以下のスワップの単純なケースであることです。

Answer 1

5 が選択されているのは、反復が O(n) に解決される最小値であるためです。7 も同様に機能しますが、遅くなる傾向があります。

より具体的には、入力をサイズ 5 のブロックに分割すると、次の繰り返しになります。

T(n) ≤ T(n/5) + T(7n/10) + O(n)

仕事はレベルごとに幾何学的に減衰するため、これは O(n) に解決されます。

サイズ 3 のブロックを使用すると、

T(n) ≥ T(n/3) + T(2n/3) + O(n)

これは Ω(n log n) に解決されます。

サイズ 7 のブロックを選択すると、

T(n) ≤ T(n / 7) + T(5n / 7) + O(n)

仕事が幾何学的に減衰するため、これも O(n) に解決されます。ただし、big-O 項の定数は 5 の場合よりも大きくなります。これは、サイズ 7 の n/7 ブロックの並べ替えと中央値の取得は、サイズ 5 の n/5 ブロックの並べ替えと中央値の取得よりも手間がかかるためです。 、5 ブロックのケースがより一般的に使用されます。

お役に立てれば！