复选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

该怎么说 我觉得电机丙的题目很鸡掰 有时候要考虑极端情况有时候不用我其实是看题目的语气决定答案的反正观念就是上面那些 要选啥就看个人造化了哈哈哈哈