因为找不到没有答案,再加上三题都很不确定
所以想要问看看大家
16.
https://imgur.com/3blBUjt
这题我觉得ac是对的
但是不是很确定
我想说a应该是对的没错
b的话我想说addrA+1跟+1000花的时间严格来说应该不一样?
但又感觉好像小到几乎可以说是一样的?
c的话我也不确定,但我觉得是对的,只是有些data structure用array可能效能会很差?
所以我会选D
17.
https://imgur.com/rh3Sj3d
这题我也不太确定时间复杂度要如何思考
我的想法是a是错的,因为向量维度如果不是一维,时间应该不会是O(n)
然后bc是对的 选E
18.
https://imgur.com/gr0kh8e
这题我会选D,但也不是很确定@@
谢谢
等等我想一下XD改一下 应该是D才对 Array任何位置存取 应该都是O(1)关于16的c 他是说Array是基本的资料结构可以用在任何的资料结构 我想应该是没有什么瑕疵才对只是影响解决问题的效能差异而已 基本上都可拿来应用
看错17a的叙述了,length=n的话应该是错的
作者:
FRAXIS (喔喔)
2017-12-23 20:56:0018a failure function 只依赖 pat 所以这到底是算对还是算错? 用 pat 和 text 当然也算的出 failure function..17 题 对于 sparse 的情况 空间复杂度应该是 O(m)?
作者:
sarsman (DeNT15T♠)
2017-12-23 22:39:00我觉得17a可选,如果是常数维度就都还在theta(n)的范围内18a应该是错的应该是pat or text
作者:
sarsman (DeNT15T♠)
2017-12-24 00:13:00后来想想的确是w大所说的那样@@不过题目说是vector的话就只会有一维吧
作者: andy6666 (Andy) 2017-12-24 13:57:00
这题交大给DAE16 array支援random access 所以时间是一样的17 这题我是认为因为你还得去找跟你相符合的相加 所以是O(mn)18 a错在and 要改or 然后其余两个林立宇kmp有写 必看网上爬文应该有考古题有到105的
作者:
yaya517 (Abby)
2017-12-24 15:50:00网络上找了很久 可以请问楼上大大哪里找到交大给的解答吗
作者: andy6666 (Andy) 2017-12-24 15:56:00
作者:
yaya517 (Abby)
2017-12-24 16:19:00谢谢楼上大大 这份好多~