[理工] 資結交大101 linked list shi359 PTT批踢踢實業坊

作者: shi359 (歸人還是過客) 2016-08-01 22:49:06

交大 101 年的弟五大題
http://i.imgur.com/puz4trc.jpg
14 15 沒問題
有問題的是 13 題
linked list 不是要一個一個 traverse 嗎
為什麼時間複雜度不會是 O(m+n/m) 而是 O(logm + n/m) 呢?
謝謝

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-08-01 23:56:00

是至少要 m/2 個嗎? 因為上面寫 order m 就是 m 個 int阿 ... 最多 m 個抱歉我把題目跟上面舉例的圖搞混了那我清楚了感謝 m(_ _)m

作者: shi359 (歸人還是過客) 2016-08-01 23:52:00

每個 node 有 m/2 個 int

作者: shi359 (歸人還是過客) 2016-08-01 23:45:00

是唷

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-08-01 23:47:00

感謝看不太懂 "each node is of m/2 integers" 這句話的意思?

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2016-08-01 23:40:00

請問 n/m 是為了找到適合的node所花的時間嗎?

作者: ken52011219 (呱) 2016-08-01 23:09:00

看到這種出法讓我想起去年交大考卷根本地獄...

作者: krusnoopy (push) 2016-08-01 23:06:00

同意樓上,題目有假設說每個node內的資料按照順序排好了

作者: gary19941208 2016-08-01 23:03:00

不確定對不對，我的想法是因為每個node裡是用array，而且已經從小排到大，所以node內部可以用binary search，所以是logm

繼續閱讀