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

看板Grad-ProbAsk作者 (斯蓋比)時間10年前 (2014/02/21 00:28), 編輯推噓5(5推 0噓 9→)
留言14則, 5人參與, 最新討論串10/19 (看更多)
想問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
→
02/21 09:45, , 1F
不知 我也覺得 O(nlogn) 是對的...
02/21 09:45, 1F
推
02/21 10:09, , 2F
link在切的時候就會慢很多了吧？
02/21 10:09, 2F
→
02/21 10:09, , 3F
array只要O(1) link要O(n)?
02/21 10:09, 3F
→
02/21 10:37, , 4F
merge sort 是用recurrence 在切跟在接的時間應該是一樣吧
02/21 10:37, 4F
→
02/21 10:38, , 5F
都是O(nlog n)
02/21 10:38, 5F
→
02/21 10:41, , 6F
http://ppt.cc/BJNe 8的話也是切三輪 接三輪 好怪R
02/21 10:41, 6F
推
02/21 11:08, , 7F
但在recurrence切的時候array可以直接給mid
02/21 11:08, 7F
→
02/21 11:08, , 8F
link必須從頭找到中間的位置？我的想法是這樣
02/21 11:08, 8F
推
02/21 11:19, , 9F
不用切啊，直接做就好。
02/21 11:19, 9F
→
02/21 11:21, , 10F
http://ppt.cc/aL3M 這篇拉到最底O(nlog n)
02/21 11:21, 10F
推
02/21 11:51, , 11F
看了sky大給的code裡 用fast slow切的時間一樣是nlogn
02/21 11:51, 11F
→
02/21 11:51, , 12F
所以加起來一樣O(nlogn) 一開始想錯了QQ
02/21 11:51, 12F
→
02/21 11:52, , 13F
感謝大家指正!!!
02/21 11:52, 13F
推
02/21 14:52, , 14F
所以是O(nlogn)囉? 所以要選?
02/21 14:52, 14F
‣ 更多 skybee 的文章
文章代碼(AID): #1J1YqPpQ (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 10 之 19 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共19篇)
‣ 更多 skybee 的文章
文章代碼(AID): #1J1YqPpQ (Grad-ProbAsk)