作者bochengchen (LFII)
看板Grad-ProbAsk
標題[理工] 101交大資演
時間Sun Dec 1 14:34:43 2019
各位大大好，小弟有幾個問題想問
1.
https://imgur.com/kXTsauq.jpg
第13題的B跟C 要怎麼選呢? 為甚麼會是logm呢?
2.
https://imgur.com/k3kgqYc.jpg
第51題 這個binomial coefficient represent integral的特性是什麼呢?
3.
https://imgur.com/bkw2Tht.jpg
第54題的time complexity該怎麼算呢?
麻煩各位大大了!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.39.113.93 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1575182085.A.E4F.html
2F：推 zuchang: 第三 這是prim’s algo 12/01 15:32
3F：推 zuchang: 啊 第一題還能再降 剛看答案是B 等其他人的方法 12/01 15:36
4F：→ zuchang: 啊 在一個node中找x 因為排序過 所以用二元搜尋 所以logm 12/01 15:38
5F：→ zuchang: 就可以 12/01 15:38
6F：推 mi981027: 第一題 從第一個node開始 每次都直接比最後一個值 12/01 15:56
7F：→ mi981027: 如果x比較大就到下個node 比較小就在當前node做bs 12/01 15:56
8F：→ mi981027: worst case會比2n/m個 12/01 15:56
9F：→ mi981027: 到最後一個node後 再做binary search 12/01 15:56
10F：→ mi981027: 總共是O(log(m/2)+2n/m) 12/01 15:56
這邊沒有想到要用binary search感謝mi大~
感謝gash大! 我來研究研究
13F：→ mi981027: 第二題的e是錯的 這種表示法會是唯一的 這也說明了這個 12/01 17:59
14F：→ mi981027: 可以用greedy來解 先找出最大的a, 再找b, 再找c 12/01 17:59
這個證明好厲害阿! 在考試的時候遇到這種題目也來不及想出來了吧!!
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:34:16
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:34:43
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:36:51
※ 編輯: bochengchen (114.39.113.93 臺灣), 12/02/2019 01:51:41