[理工] 资结交大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

继续阅读