処理時間が線形であることの証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 15:10 UTC 版)
「中央値の中央値」の記事における「処理時間が線形であることの証明」の解説
中央値の計算は再帰呼び出しとなっているが、最悪の場合でも線形である。なぜなら、 T ( n ) {\displaystyle T(n)} をn個の配列に中央値の中央値を適用したクイックセレクトを適用した時の処理時間とすると、 T ( n ) ≤ T ( 2 10 n ) + C n + T ( 7 10 n ) {\displaystyle T(n)\leq T\left({\frac {2}{10}}n\right)+Cn+T\left({\frac {7}{10}}n\right)} だからである。ここで T ( 2 10 n ) {\displaystyle T\left({\frac {2}{10}}n\right)} の項は、各小配列から中央値のみを抽出した配列（要素数が必ず元の配列のの要素数の2割）から真の中央値、つまりピボット値を計算するための処理時間（中央値の計算は選択アルゴリズムの特別な場合であり、クイックセレクトの再帰呼び出しで計算可能であるので）：計算手法で示したコード上では、初回の反復におけるPivotの処理時間 C n {\displaystyle Cn} の項は、ピボット値を使って配列を2分割して次の探索対象の配列を作成するための処理時間（ピボット値と各小配列から中央値のみを抽出した配列の各要素との比較処理であり、比較処理は定数時間 O ( 1 ) {\displaystyle \mathrm {O} (1)} で計算可能であるので）：計算手法で示したコード上では、初回の反復におけるPartitionの処理時間 T ( 7 10 n ) {\displaystyle T\left({\frac {7}{10}}n\right)} の項は、分割した後の次の探索対象の配列（要素数は最悪でも元の配列の要素数の7割）でk番目に大きい要素を計算する最大の処理時間（クイックセレクトを再帰的に適用することと等価なので）：計算手法で示したコード上では、次の反復以降にかかる処理時間。 この式は簡単に解けて、最終的には以下のように線形時間 O ( n ) {\displaystyle \mathrm {O} (n)} であることを示すことができる。 T ( n ) ≤ 10 C n ∈ O ( n ) {\displaystyle T(n)\leq 10Cn\in \mathrm {O} (n)}
※この「処理時間が線形であることの証明」の解説は、「中央値の中央値」の解説の一部です。
「処理時間が線形であることの証明」を含む「中央値の中央値」の記事については、「中央値の中央値」の概要を参照ください。
- 処理時間が線形であることの証明のページへのリンク
