作者joywilliamjo (joywilliamjoy)
看板Grad-ProbAsk
標題[理工] 108 台大電機丙 複選題
時間Tue Dec 8 17:00:04 2020
複選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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1607418006.A.F31.html
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:11:17
1F：推 jimmylin1024: 15題 B還是可以用 只是結果好不好的問題 C不會變快12/08 17:27
2F：→ jimmylin1024: 因為刪掉資料後會在對應的slot做記號 才不會影響之 12/08 17:27
3F：→ jimmylin1024: 後的search (才不會還沒probe到要找到資料就因為pro12/08 17:27
4F：→ jimmylin1024: be到空的slot 而回傳null ）12/08 17:27
所以15比較像CE？
5F：推 jimmylin1024: 13題E是對的 topological sort可以是O(E+V) 但是要12/08 17:30
6F：→ jimmylin1024: 對graph做預處理12/08 17:30
7F：→ mathtsai: topological sort本來就是O(E+V)啊12/08 17:33
8F：→ jimmylin1024: 14題E input 一開始的排列不會影響radix sort 的時12/08 17:33
9F：→ jimmylin1024: 間複雜度 因為每一個digit 都一樣會是O(n)12/08 17:33
10F：推 jimmylin1024: 16 A 如果你把式子寫成 T(n) = T(n/k) + O(1) k是正12/08 17:38
11F：→ jimmylin1024: 整數， 就是O(logn)12/08 17:38
了解，用master theory想比較快
是說如果這題直接空白或是寫無解到底是扣兩分還是全錯啊
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 17:50:42
12F：→ aa871220: 15（c) CLRS關於quadratic probing是這樣說的：12/08 18:53
13F：→ aa871220: Hash function :h(k,I)=(h’(k)+c1i +c2i^2)mod m12/08 18:53
14F：→ aa871220: 要使slot被full use 必須特別挑選c1 c2與m之值12/08 18:53
15F：→ aa871220: 換句話說你可以隨便找個反例的slot數量與hash finction12/08 18:53
16F：→ aa871220: 更正是D12/08 18:54
17F：→ aa871220: （C) 像一樓說的 會加入一個delete node 在原本的slot 12/08 18:57
18F：→ aa871220: 所以你其他與被刪除的node之proving sequence一樣時 不12/08 18:57
19F：→ aa871220: 會改變要probing的數量 所以不會變快 答案應該只有E 12/08 18:57
總結一下
14.BCE
15.E
16.A
20F：推 jimmylin1024: aa大 這樣的話D選項可以選吧（？）雖然可以找到反例 12/08 19:03
不行哦，照題目英文翻譯是linear和quadratic要所有情況都能應付，我的理解是有例外
反例這個選項就不能選
21F：→ jimmylin1024: 但是只要特別挑選的話 是可以probe到全部slot 的（ 12/08 19:03
22F：→ jimmylin1024: ？）還是我哪裡有理解錯誤麻煩指正QQ 12/08 19:03
你這個就比較像
https://i.imgur.com/ALwv421.jpg
比較像英文理解問題而不是觀念理解
QQ
23F：→ aa871220: 該怎麼說 我覺得電機丙的題目很雞掰 有時候要考慮極端情12/08 19:06
24F：→ aa871220: 況有時候不用 12/08 19:06
25F：→ aa871220: 我其實是看題目的語氣決定答案的 12/08 19:06
26F：→ aa871220: 反正觀念就是上面那些 要選啥就看個人造化了哈哈哈哈 12/08 19:06
真的覺得有夠麻煩
還有電機丙是非選擇的notation= =
比如說題目最逼近的是O(n)，但要是題目問O(n^n)對不對的話得選對
※ 編輯: joywilliamjo (42.74.26.5 臺灣), 12/08/2020 21:12:46