algorithm - 中央値アルゴリズムの中央値: 配列をサイズ 5 のブロックに分割する理由

Question

median-of-medians アルゴリズムでは、配列をサイズ 5 のチャンクに分割する必要があります。アルゴリズムの発明者がどのようにしてマジック ナンバー '5' を思いついたのか疑問に思っています。他の何か？

Answer 1

アルゴリズムでは、数値は 3 (もちろん奇数) よりも大きくなければなりません。5 は 3 より大きい最小の奇数です。したがって、5 が選択されました。

Answer 2

medians-of-medians アルゴリズムの wiki ページの「Proof of O(n) running time」セクションを確認すると、次のようになります。

中央値のリストはリストのサイズの 20% であるため、中央値を計算する再帰呼び出しは最悪の場合の線形動作を超えませんが、他の再帰呼び出しはリストの最大 70% で再帰し、実行時間を短縮します。

O(n) 項 cn は分割作業用です (各要素を一定回数訪れて、それらを n/5 グループに形成し、O(1) 時間で各中央値を取得します)。このことから、帰納法を使用して、次のことを簡単に示すことができます。

それは、なぜなのかを理解するのに役立つはずです。