推 kyuudonut: 你並不知道第(n/5)堆的 median 就是 m-of-m's 阿 10/04 00:26
我的想法是...
假設有100個數(n=100)，分成(n/5)堆，也就是5個5個一堆總共20堆(這20堆尚未sorting)
然後開始對第一堆sorting直到第10堆的時候，我就知道這堆的median
就是median中的median
→ ken52011219: 有例題嗎 @@? 10/04 00:26
→ kyuudonut: 洪逸並沒有教 substitution 吧? master前面不都展開嗎 10/04 00:27
推 k2shouai: substitution就是代入展開R 10/04 00:31
→ kyuudonut: 喔ㄛ 了解! 10/04 00:36
推 joy7658x348: substitution是拿來證明的吧？展開代入跟master thm 10/04 00:37
→ joy7658x348: 對演算來說都只能算是“猜”答案吧 真正要證明還是只 10/04 00:37
→ joy7658x348: 有substitution 10/04 00:37
據我所了解，展開帶入就是substituation，不知道為什麼這句話感覺怪怪的
→ kyuudonut: 那就是如原PO講的那樣 各自證 upper & lower bound 10/04 00:37
※ 編輯: a19930301 (220.142.123.1), 10/04/2016 08:10:32
推 kyuudonut: 為什麼你會覺得第十堆的median就是 m-of-m's? 10/04 08:48
→ kyuudonut: 另外我確認了一下 substitution 是證明的方法沒錯 10/04 08:48
→ kyuudonut: 例如有10堆的median: 8,8,8,8,3,5,4,4,4,4 10/04 08:51
→ kyuudonut: 你說第(10/2)堆是median 這邊是3 可是並不是R 是4才對 10/04 08:54
推 kyuudonut: 呃,,,抱歉 剛睡醒有點昏 subst.似乎就是帶入展開XD 10/04 08:57
→ kyuudonut: 只是洪逸在教這段時 並沒有像演算法那樣很嚴謹的證明 10/04 08:57
→ kyuudonut: 所以我有點搞混 拍謝拍謝XD 10/04 08:58
哈哈 不知道為什麼你回答的方式跟我好像XD
→ ken52011219: 昨天快睡著了 QQ 10/04 10:03
→ ken52011219: Substitution 有些題目依照題意 可以改成 T(n) <= .. 10/04 10:04
→ ken52011219: 例如像是 floor 之類的 此時 會算出 為big oh 10/04 10:05
→ ken52011219: 假如 依題目列出 T(n) = ... 就為 THETA 10/04 10:07
→ ken52011219: 這些 楓葉本 3rd 83頁有類似講解 10/04 10:08
請問什麼是 楓葉本 ?
推 ken52011219: 假如題目單純給 = 就是THETA 但 假如此等式中有其他 10/04 10:15
→ ken52011219: 未知數 就要考慮它是在UPPER or lower bound 來決定 10/04 10:15
→ ken52011219: 它的等式 實際上是大於等於 還是 小於等於 10/04 10:16
→ ken52011219: 如同 Ky大連結內 那個T(n)式子 10/04 10:19
不過還是感謝解答
推 aa06697: 每堆之間沒有關係啊 你沒有得出每堆的中位數 怎麼求得中 10/04 13:46
→ aa06697: 位數的中位數（再排序堆）@@ 10/04 13:46
我大概了解你的意思了，我還想說再排序時順便比較我要的數
但..這樣最少時間也要O(nlogn)
※ 編輯: a19930301 (36.239.191.30), 10/05/2016 23:13:55
推 ken52011219: 楓葉本是 Algorithem 的聖經書 台清交都用這本 10/11 15:32