[理工] 101交大資演

看板Grad-ProbAsk作者 (LFII)時間4年前 (2019/12/01 14:34), 4年前編輯推噓6(6推 0噓 8→)
留言14則, 3人參與, 4年前最新討論串4/4 (看更多)
各位大大好，小弟有幾個問題想問 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1575182085.A.E4F.html
推
12/01 15:21, 4年前 , 1F
12/01 15:21, 1F
推
12/01 15:32, 4年前 , 2F
第三 這是prim’s algo
12/01 15:32, 2F
推
12/01 15:36, 4年前 , 3F
啊 第一題還能再降 剛看答案是B 等其他人的方法
12/01 15:36, 3F
→
12/01 15:38, 4年前 , 4F
啊 在一個node中找x 因為排序過 所以用二元搜尋 所以logm
12/01 15:38, 4F
→
12/01 15:38, 4年前 , 5F
就可以
12/01 15:38, 5F
推
12/01 15:56, 4年前 , 6F
第一題 從第一個node開始 每次都直接比最後一個值
12/01 15:56, 6F
→
12/01 15:56, 4年前 , 7F
如果x比較大就到下個node 比較小就在當前node做bs
12/01 15:56, 7F
→
12/01 15:56, 4年前 , 8F
worst case會比2n/m個
12/01 15:56, 8F
→
12/01 15:56, 4年前 , 9F
到最後一個node後 再做binary search
12/01 15:56, 9F
→
12/01 15:56, 4年前 , 10F
總共是O(log(m/2)+2n/m)
12/01 15:56, 10F
這邊沒有想到要用binary search感謝mi大~
推
12/01 17:21, 4年前 , 11F
12/01 17:21, 11F
感謝gash大! 我來研究研究
推
12/01 17:54, 4年前 , 12F
12/01 17:54, 12F
→
12/01 17:59, 4年前 , 13F
第二題的e是錯的 這種表示法會是唯一的 這也說明了這個
12/01 17:59, 13F
→
12/01 17:59, 4年前 , 14F
可以用greedy來解 先找出最大的a, 再找b, 再找c
12/01 17:59, 14F
這個證明好厲害阿! 在考試的時候遇到這種題目也來不及想出來了吧!! ※ 編輯: 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
‣ 更多 bochengchen 的文章
文章代碼(AID): #1Tury5vF (Grad-ProbAsk)
‣ 更多 bochengchen 的文章
文章代碼(AID): #1Tury5vF (Grad-ProbAsk)