複選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

15題 B還是可以用 只是結果好不好的問題 C不會變快因為刪掉資料後會在對應的slot做記號 才不會影響之後的search (才不會還沒probe到要找到資料就因為probe到空的slot 而回傳null ）13題E是對的 topological sort可以是O(E+V) 但是要對graph做預處理

topological sort本來就是O(E+V)啊

14題E input 一開始的排列不會影響radix sort 的時間複雜度 因為每一個digit 都一樣會是O(n)16 A 如果你把式子寫成 T(n) = T(n/k) + O(1) k是正整數， 就是O(logn)

15（c) CLRS關於quadratic probing是這樣說的：Hash function :h(k,I)=(h’(k)+c1i +c2i^2)mod m要使slot被full use 必須特別挑選c1 c2與m之值換句話說你可以隨便找個反例的slot數量與hash finction更正是D（C) 像一樓說的 會加入一個delete node 在原本的slot所以你其他與被刪除的node之proving sequence一樣時 不會改變要probing的數量 所以不會變快 答案應該只有E

aa大 這樣的話D選項可以選吧（？）雖然可以找到反例但是只要特別挑選的話 是可以probe到全部slot 的（？）還是我哪裡有理解錯誤麻煩指正QQ

該怎麼說 我覺得電機丙的題目很雞掰 有時候要考慮極端情況有時候不用我其實是看題目的語氣決定答案的反正觀念就是上面那些 要選啥就看個人造化了哈哈哈哈