]>
アルゴリズムイントロダクション 第 9 章 中央値と順序統計量 (その 1)
中央値と順序統計量 (その 1)
nanto_vi (TOYAMA Nao)
予定
- 順序統計量とは
- 選択問題とは
- 最小値と最大値
- 平均線形時間選択アルゴリズム
- 最悪線形時間選択アルゴリズム
順序統計量とは
- i 番目の順序統計量
- i 番目に小さい要素
- 最小値
- 1 番目の順序統計量
- 最大値
- n 番目の順序統計量
- 中央値
-
番目の順序統計量 (n が奇数)
-
番目 (小さいほうの中央値) と
番目 (大きいほうの中央値) の順序統計量 (n が偶数)
選択問題とは
- 順序統計量を求める問題
- ここでは集合の要素はすべて異なると仮定
- 選択問題を解く
- ソートした結果の i 番目を返す
-
計算時間は
-
i が特定の値なら
で解ける
- 一般の選択問題の場合は?
最小値と最大値
最小値 (最大値) のみを求める
-
回の比較で結果が求まる
-
実行時間は
最小値と最大値を同時に求めるには
- 別々に求める
- 1 要素に対して 2 回の比較
-
全体で
回の比較
- 要素を対にし、まず対の中で比較
- 2 要素に対して 3 回の比較
-
全体で
回の比較
平均線形時間選択アルゴリズム
- 乱択アルゴリズム
-
平均実行時間が線形 (
)
実行時間の評価
Randomized-Select の実行時間を
とする。
ところで、
とすると、
Randomized-Select の 1 回の呼び出しにおける実行時間は、
この期待値は、
右辺第 2 項はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
、ある定数 d に対して
で
と仮定すると、
ここで、
とすると、
で
だから、