作者defsrisars (阿转)
看板Grad-ProbAsk
标题[理工] 105交大资演 第6题 关於array
时间Sat Dec 23 19:01:46 2017
因为找不到没有答案，再加上三题都很不确定
所以想要问看看大家
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，但也不是很确定@@
谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 61.230.52.157
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1514026909.A.6B6.html
1F：推 jerry900287: 关於16提应该是 E 12/23 19:37
2F：推 winiel559: 17a是对的吧 12/23 19:39
3F：→ jerry900287: 等等我想一下XD 12/23 19:39
4F：→ jerry900287: 改一下 应该是D才对 Array任何位置存取 应该都是O(1) 12/23 19:41
5F：→ jerry900287: 关於16的c 他是说Array是基本的资料结构 12/23 19:42
6F：→ jerry900287: 可以用在任何的资料结构 我想应该是没有甚麽瑕疵才对 12/23 19:43
7F：→ jerry900287: 只是影响解决问题的效能差异而已 基本上都可拿来应用 12/23 19:44
8F：推 winiel559: 看错17a的叙述了，length=n的话应该是错的 12/23 19:53
9F：推 FRAXIS: 18a failure function 只依赖 pat 所以这到底是算对还是 12/23 20:56
10F：→ FRAXIS: 算错? 用 pat 和 text 当然也算的出 failure function.. 12/23 20:56
11F：推 FRAXIS: 17 题 对於 sparse 的情况 空间复杂度应该是 O(m)? 12/23 20:59
12F：推 sarsman: 我觉得17a可选，如果是常数维度就都还在theta(n)的范围内 12/23 22:39
13F：→ sarsman: 18a应该是错的 12/23 22:49
14F：→ sarsman: 应该是pat or text 12/23 22:57
15F：推 winiel559: 二维就直接跳到n^2了耶 几维就几次方r 12/23 23:46
16F：推 sarsman: 後来想想的确是w大所说的那样@@ 12/24 00:13
17F：→ sarsman: 不过题目说是vector的话就只会有一维吧 12/24 00:13
18F：推 kssdpp222: 向量是1*n 怎麽会变二维 12/24 00:47
19F：推 winiel559: 因为强调是线代的向量所以一定是一维吗？ 12/24 08:14
20F：推 olen0622: 猜DAE 12/24 09:54
21F：推 andy6666: 这题交大给DAE 12/24 13:57
22F：→ andy6666: 16 array支援random access 所以时间是一样的 12/24 13:58
23F：推 andy6666: 17 这题我是认为因为你还得去找跟你相符合的相加 所以 12/24 14:00
24F：→ andy6666: 是O(mn) 12/24 14:00
25F：→ andy6666: 18 a错在and 要改or 然後其余两个林立宇kmp有写 必看 12/24 14:01
26F：→ andy6666: 网上爬文应该有考古题有到105的 12/24 14:01
27F：推 yaya517: 网路上找了很久 可以请问楼上大大哪里找到交大给的解答吗 12/24 15:50
29F：→ andy6666: GX2x3Mmc/view?usp=drivesdk 12/24 15:56
31F：→ andy6666: 2cE9TRTg/view?usp=drivesdk 12/24 15:56
32F：→ andy6666: 两份载下来放到同个资料夹解压缩 有些没有有些有 12/24 15:57
33F：推 yaya517: 谢谢楼上大大 这份好多～ 12/24 16:19