[理工] 108 台大電機丙 複選題

看板Grad-ProbAsk作者 (joywilliamjoy)時間5年前 (2020/12/08 17:00), 5年前編輯推噓4(4推 0噓 22→)
留言26則, 3人參與, 5年前最新討論串1/1
複選14、15、16 板上討論很多但沒有個定案 那就再討論一次吧... https://i.imgur.com/lh19E8H.jpg
14題我的理解是要找worst/best/average case的時間複雜度都是一樣的演算法 E的話我之前上網背的表格時間複雜度都是 O(n*(d+r))所以我覺得答案應該是BCE 15的話BC不知道怎麼解釋 D的話我認為overflow的狀況沒被考慮進去（整個hash table都滿了依然overflow 然後16題 這題我一開始是寫沒答案 CE一定錯 D沒認真算，但有一個for loop兩個while loop估計不會是nlogn ，B的話我覺得不是O(n)就是O(n^n) 怎麼樣也不會到n^2 A我自己覺得應該是nlogn但看板上的討論應該是錯了 不知道為什麼 還希望能大家多多討論 救救沒有讀書會的人QQ 補充一下 13的E應該是對的 上網有查到O(E+V),adjacency list存 我是選CDE https://i.imgur.com/WSr1iMa.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.26.5 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607418006.A.F31.html ※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:11:17
推
12/08 17:27, 5年前 , 1F
15題 B還是可以用 只是結果好不好的問題 C不會變快
12/08 17:27, 1F
→
12/08 17:27, 5年前 , 2F
因為刪掉資料後會在對應的slot做記號 才不會影響之
12/08 17:27, 2F
→
12/08 17:27, 5年前 , 3F
後的search (才不會還沒probe到要找到資料就因為pro
12/08 17:27, 3F
→
12/08 17:27, 5年前 , 4F
be到空的slot 而回傳null ）
12/08 17:27, 4F
所以15比較像CE？
推
12/08 17:30, 5年前 , 5F
13題E是對的 topological sort可以是O(E+V) 但是要
12/08 17:30, 5F
→
12/08 17:30, 5年前 , 6F
對graph做預處理
12/08 17:30, 6F
→
12/08 17:33, 5年前 , 7F
topological sort本來就是O(E+V)啊
12/08 17:33, 7F
→
12/08 17:33, 5年前 , 8F
14題E input 一開始的排列不會影響radix sort 的時
12/08 17:33, 8F
→
12/08 17:33, 5年前 , 9F
間複雜度 因為每一個digit 都一樣會是O(n)
12/08 17:33, 9F
推
12/08 17:38, 5年前 , 10F
16 A 如果你把式子寫成 T(n) = T(n/k) + O(1) k是正
12/08 17:38, 10F
→
12/08 17:38, 5年前 , 11F
整數， 就是O(logn)
12/08 17:38, 11F
了解，用master theory想比較快 是說如果這題直接空白或是寫無解到底是扣兩分還是全錯啊 ※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:50:42
→
12/08 18:53, 5年前 , 12F
15（c) CLRS關於quadratic probing是這樣說的：
12/08 18:53, 12F
→
12/08 18:53, 5年前 , 13F
Hash function :h(k,I)=(h’(k)+c1i +c2i^2)mod m
12/08 18:53, 13F
→
12/08 18:53, 5年前 , 14F
要使slot被full use 必須特別挑選c1 c2與m之值
12/08 18:53, 14F
→
12/08 18:53, 5年前 , 15F
換句話說你可以隨便找個反例的slot數量與hash finction
12/08 18:53, 15F
→
12/08 18:54, 5年前 , 16F
更正是D
12/08 18:54, 16F
→
12/08 18:57, 5年前 , 17F
（C) 像一樓說的 會加入一個delete node 在原本的slot
12/08 18:57, 17F
→
12/08 18:57, 5年前 , 18F
所以你其他與被刪除的node之proving sequence一樣時 不
12/08 18:57, 18F
→
12/08 18:57, 5年前 , 19F
會改變要probing的數量 所以不會變快 答案應該只有E
12/08 18:57, 19F
總結一下 14.BCE 15.E 16.A
推
12/08 19:03, 5年前 , 20F
aa大 這樣的話D選項可以選吧（？）雖然可以找到反例
12/08 19:03, 20F
不行哦，照題目英文翻譯是linear和quadratic要所有情況都能應付，我的理解是有例外 反例這個選項就不能選
→
12/08 19:03, 5年前 , 21F
但是只要特別挑選的話 是可以probe到全部slot 的（
12/08 19:03, 21F
→
12/08 19:03, 5年前 , 22F
？）還是我哪裡有理解錯誤麻煩指正QQ
12/08 19:03, 22F
你這個就比較像 https://i.imgur.com/ALwv421.jpg
比較像英文理解問題而不是觀念理解 QQ
→
12/08 19:06, 5年前 , 23F
該怎麼說 我覺得電機丙的題目很雞掰 有時候要考慮極端情
12/08 19:06, 23F
→
12/08 19:06, 5年前 , 24F
況有時候不用
12/08 19:06, 24F
→
12/08 19:06, 5年前 , 25F
我其實是看題目的語氣決定答案的
12/08 19:06, 25F
→
12/08 19:06, 5年前 , 26F
反正觀念就是上面那些 要選啥就看個人造化了哈哈哈哈
12/08 19:06, 26F
真的覺得有夠麻煩 還有電機丙是非選擇的notation= = 比如說題目最逼近的是O(n)，但要是題目問O(n^n)對不對的話得選對 ※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 21:12:46
‣ 更多 joywilliamjo 的文章
文章代碼(AID): #1Vpq2Myn (Grad-ProbAsk)