※ 引述《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