Re: [理工] 100&101台大電機丙-DS
作者: skybee (斯蓋比) 2014-02-21 00:28:07
想問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
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
作者: olderbrother (哥) 2014-02-21 09:45:00
不知 我也覺得 O(nlogn) 是對的...
作者: immomo808 (momo) 2014-02-21 10:09:00
link在切的時候就會慢很多了吧？array只要O(1) link要O(n)?
作者: skybee (斯蓋比) 2014-02-21 10:37:00
merge sort 是用recurrence 在切跟在接的時間應該是一樣吧都是O(nlog n)![]()
" target="_blank" rel="nofollow">
![]()
8的話也是切三輪 接三輪 好怪R
" target="_blank" rel="nofollow"> 8的話也是切三輪 接三輪 好怪R作者: immomo808 (momo) 2014-02-21 11:08:00
但在recurrence切的時候array可以直接給midlink必須從頭找到中間的位置？我的想法是這樣
作者: A4P8T6X9 (殘廢的名偵探) 2014-02-21 11:19:00
不用切啊，直接做就好。
作者: skybee (斯蓋比) 2014-02-21 11:21:00
" target="_blank" rel="nofollow"> 這篇拉到最底O(nlog n)作者: immomo808 (momo) 2014-02-21 11:51:00
看了sky大給的code裡 用fast slow切的時間一樣是nlogn所以加起來一樣O(nlogn) 一開始想錯了QQ感謝大家指正!!!
作者: johnny87901 (autumn) 2014-02-21 14:52:00
所以是O(nlogn)囉? 所以要選?