作者Matsus (momoto 300)
看板b92902xxx
标题Re: [公告] 资料结构与演算法的Demo时间与地点公告
时间Sat Oct 23 17:02:47 2004
※ 引述《BuddhaSword (徵脚踏车~台大)》之铭言：
: 请问阿 昨天Algo上课的时候
: 老师讲了一个粗略估计 p,q 介於 3/10 * n ~ 7/10 * n
: 为什麽ㄚ
因为保证有 1/2 的组数中的 3/5个数 比y小
有 1/2 的组数中的 3/5个数 比y大
换句话说 总共有1/5的数是中位数 她们与y的大小关系都被确定
其中一半比较小 一半比较大
比较小的那些 在他们的组里面 有2/5又比他们小
所以总共 1/2 * (1/5 + 2/5) = 3/10 绝对比y小
同理 比y大的也是
: 就是分析那个找k th小的Algo
: ※ 引述《modulate (昂首千丘远)》之铭言：
: : Demo地点：538或219，
: : Demo时间：
: : 星期三 PM 1:30 ~ 2:10、PM 5:30 ~ 7:15
: : 星期四 PM 1:30 ~ 2:10、PM 5:30 ~ 7:15
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.21.13