[理工] [資聯] 105 交大資訊聯招

[ken52011219 (呱)]

大家好，想問一些問題

題組六　

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
推 blue14753: 23的C 假如現在有7 8 10，我要差9a和9b
→ blue14753: 我9a會先插在8的後面變7 8 9a 10，接下來換9b
→ blue14753: 根據題目會變成7 8 9b 9a 10，就不stable了，
→ blue14753: 所以less應該改成less and equal
        了解了，b大的解釋感覺比較合理，謝謝！

推 yupog2003: 17(B)，我對m out of n non-zero的理解是n個term裡面
→ yupog2003: 有m個是非0的
        查了一下 Out of 的用法好像是指「範圍之外」

→ yupog2003: time complexity因為次想加一個term就要先去找相同
→ yupog2003: index的來加，所以time complexity為O(m^2)
        應該是不用做 sort 吧 @@? spare vector 的值 已經夠少了

→ yupog2003: 不過如果有先排序做優化的話也是可以達到O(m)拉...
→ yupog2003: 所以我也沒很肯定這樣解釋是否正確
→ yupog2003: non-linear會不會就是在說divide and conquer或是建
→ yupog2003: heap這種？time complexity為n^2的都是在array上操作
→ yupog2003: 而已，也許這就是linear operator?我猜的拉...
※ 編輯: ken52011219 (36.224.38.221), 01/07/2017 21:48:34
→ yupog2003: out of如果前後都接數字的話可以當分子分母用喔
        感謝提醒，這樣子感覺 空間複雜度為theta(m) , 時間複雜度為 theta(n)??
※ 編輯: ken52011219 (36.224.38.221), 01/07/2017 23:02:12
→ Gabino: non-linear operator 應該是非比較式運算
        我在思考可能(? 其實無關是否 non-linear operator or linear operator
        只要使用 decision tree 就可以壓低 theta(nlogn) 的下界了 (??

        不知道是不是這個意思
※ 編輯: ken52011219 (36.224.38.221), 01/08/2017 19:20:45
推 hibiscus520: 我在想兩個向量m個位置在原本n裡面不同的話
→ hibiscus520: 相加應該會超過theta(m)
推 tna4568: Ga大說的沒錯 就是沒用到比較數值的方式喔