]>
アルゴリズムイントロダクション 第 9 章 中央値と順序統計量 (補足)
中央値と順序統計量 (補足)
nanto_vi (TOYAMA Nao)
4 つずつのグループに分割した場合
x より大きい要素、小さい要素はそれぞれ少なくとも
,
個存在するから、
,
の要素数はそれぞれ高々
,
個。よって、
はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
と仮定すると、
よって、
を
で抑えきれない。
6 つずつのグループに分割した場合
x より大きい要素、小さい要素はそれぞれ少なくとも
,
個存在するから、
,
の要素数はそれぞれ高々
,
個。よって、
はある定数 a を用いて
で抑えられる。ここで、ある定数 c に対して
と仮定すると、
ここで、
とすると、
で
だから、
Lazy-Select
Select は
に隠された定数が大きいため、一般には Randomized-Select または Lazy-Select が用いられることが多いらしい。
Randomized-Partition
スタッフロール
- Slide Composer
- nanto_vi
- Master of Ceremony
- motemen
- Venue Provider
- Hatena Inc.
- Rehearsal Collaborator
- NISHIDA Atsushi
- Exploded
- hakobe932
- ninjinkun
- ujihisa
- And You