[理工] [資結] 105 交大資訊聯招
大家好，想問一些問題
題組六
http://imgur.com/a/9fPZr
(17)
B選項：
因為題目所說「m out of n non-zero」 代表當 array store
超過 n 之後就不會再繼續存 n + (m - n) th ~ m th 的值了
故 space complexity 為 θ(n)
time complexity 為 θ(m)
這樣的觀念有誤嗎？
C選項：
因為兩 vector 都為sparse vector，代表其matrix 中的值
大部分都為 zero，其儲存辦法為：紀錄某行某列為某值即可
故 space complexity 為 O(n) 趨於 θ(1)
time complexity 為 θ(m)
這樣的觀念有誤嗎？
題組八
http://imgur.com/a/Mqhpw
(23)
C選項：
這裡的反例是指 j 有可能比 i 大的例子嗎？
因為 insertion sort 為 stable 所以其值大小關係有可能為 等於
http://imgur.com/a/Q8dmm
(24)
D選項：
有點不太了解 non-linear operator ，請問有人可以舉例一下嗎？
感謝各位
--
有一個香錦囊，是從一個神話般的守軍的血屍頂上剝下的。那一次我們部隊遭受從未
有過的頑強抵抗，我們犧牲了三個艦隊，一個裝甲師和無以數計小組推進的敢死排，才摧
毀了那處隘口的碉堡。但是竟然發現，使我們遭受如此慘烈傷亡的守軍，總數只有一人。
士兵們起鬨地在他胸前發現這枚香袋，大家都相信這是一枚具有神奇力量的護身符。
我們把他的頭顱砍斷，取下香袋，剝開，
裡面一張被血浸紅的宣紙竟用漢字娟娟秀秀四個整齊的楷書寫著－「盼君早歸。」
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.38.221
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483794742.A.DAC.html
※ 編輯: ken52011219 (36.224.38.221), 01/07/2017 21:21:32
推
01/07 21:23, , 1F
01/07 21:23, 1F
→
01/07 21:23, , 2F
01/07 21:23, 2F
→
01/07 21:23, , 3F
01/07 21:23, 3F
→
01/07 21:23, , 4F
01/07 21:23, 4F
了解了，b大的解釋感覺比較合理，謝謝！
推
01/07 21:30, , 5F
01/07 21:30, 5F
→
01/07 21:31, , 6F
01/07 21:31, 6F
查了一下 Out of 的用法好像是指「範圍之外」
→
01/07 21:31, , 7F
01/07 21:31, 7F
→
01/07 21:32, , 8F
01/07 21:32, 8F
應該是不用做 sort 吧 @@? spare vector 的值 已經夠少了
→
01/07 21:33, , 9F
01/07 21:33, 9F
→
01/07 21:33, , 10F
01/07 21:33, 10F
→
01/07 21:38, , 11F
01/07 21:38, 11F
→
01/07 21:39, , 12F
01/07 21:39, 12F
→
01/07 21:39, , 13F
01/07 21:39, 13F
※ 編輯: ken52011219 (36.224.38.221), 01/07/2017 21:48:34
→
01/07 21:49, , 14F
01/07 21:49, 14F
感謝提醒，這樣子感覺 空間複雜度為theta(m) , 時間複雜度為 theta(n)??
※ 編輯: ken52011219 (36.224.38.221), 01/07/2017 23:02:12
→
01/08 14:06, , 15F
01/08 14:06, 15F
我在思考可能(? 其實無關是否 non-linear operator or linear operator
只要使用 decision tree 就可以壓低 theta(nlogn) 的下界了 (??
不知道是不是這個意思
※ 編輯: ken52011219 (36.224.38.221), 01/08/2017 19:20:45
推
01/08 23:48, , 16F
01/08 23:48, 16F
→
01/08 23:48, , 17F
01/08 23:48, 17F
推
01/12 14:19, , 18F
01/12 14:19, 18F