作者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/cn.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