]>
アルゴリズムイントロダクション 第 9 章 中央値と順序統計量 (その 2)
中央値と順序統計量 (その 2)
nanto_vi (TOYAMA Nao)
最悪線形時間選択アルゴリズム
-
最悪実行時間が線形 (
)
実行時間の評価
x より大きい要素、小さい要素はそれぞれ少なくとも
個存在するから、
,
の要素数はいずれも高々
個。
Select の実行時間を
とすると、各ステップの実行時間は、
ここで、ある定数 d に対して
で
と仮定すると、
はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
と仮定すると、
ここで、
とすると、
で
だから、
3 つずつのグループに分割した場合
x より大きい要素、小さい要素はそれぞれ少なくとも
個存在するから、
,
の要素数はいずれも高々
個。よって、
はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
と仮定すると、
よって、
を
で抑えきれない。
7 つずつのグループに分割した場合
x より大きい要素、小さい要素はそれぞれ少なくとも
個存在するから、
,
の要素数はいずれも高々
個。よって、
はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
と仮定すると、
ここで、
とすると、
で
だから、
ただし、ステップ 2 の実行時間が、5 つずつのグループに分割した場合は
なのに対し、7 つずつのグループに分割した場合は
なので、定数 a の値はこちらのほうが大きい。
参考文献
- T. H. Cormen, C. H. Leiserson, R. L. Rivest, C. Stein, 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一, アルゴリズムイントロダクション 改定 2 版 第 1 巻 数学的基礎とデータ構造, 近代科学社
- 岩間一雄, アルゴリズム理論入門, 昭晃堂
- 茨木俊秀, C によるアルゴリズムとデータ構造, 昭晃堂