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