Re: [理工] 100&101台大電機丙-DS

[skybee (斯蓋比)]

想問100 第8題的D選項

double linked list 的話做一次O(n)

那做O(log n)回 不就是O(nlog n)

為什麼這選項不能選?


※ 引述《BuliBuchi (不離不棄)》之銘言：
: http://tinyurl.com/cpkzwuq 101
: http://tinyurl.com/cd77xza 100
: 想跟大家對個答案
: 不過寫起來蠻不順的
: 所以有錯請大大指教
: 101
: 單選
: 1~5.AECBD
: 多選
: 6.AD
: 7.CDE
: 8.AB
: 9.ADE
: 10.CDE
: 11.AB
: 100
: 單選
: 1~5.EACBD 6看不懂題目..
: 多選
: 7.CDE
: 8.BC
: 9.E
: 10.CDE
: 11.ABCD
: 12.AE
: 13.E
: 14.ABCD
: 15.ABE
: 16.B

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.244.171
→ olderbrother:不知  我也覺得 O(nlogn) 是對的...
推 immomo808:link在切的時候就會慢很多了吧？
→ immomo808:array只要O(1)   link要O(n)?
→ skybee:merge sort 是用recurrence 在切跟在接的時間應該是一樣吧
→ skybee:都是O(nlog n)
→ skybee:http://ppt.cc/BJNe 8的話也是切三輪 接三輪 好怪R
推 immomo808:但在recurrence切的時候array可以直接給mid
→ immomo808:link必須從頭找到中間的位置？我的想法是這樣
推 A4P8T6X9:不用切啊，直接做就好。
→ skybee:http://ppt.cc/aL3M 這篇拉到最底O(nlog n)
推 immomo808:看了sky大給的code裡 用fast slow切的時間一樣是nlogn
→ immomo808:所以加起來一樣O(nlogn)  一開始想錯了QQ
→ immomo808:感謝大家指正!!!
推 johnny87901:所以是O(nlogn)囉? 所以要選?