[理工] [資結] 100清大計算機科學

看板Grad-ProbAsk作者 (Larry)時間11年前 (2013/01/17 20:52), 編輯推噓0(0推 0噓 3→)
留言3則, 2人參與, 最新討論串1/1
http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/100/2201.pdf 第二題(a)答案是O(nlog(k/n)+n/k*k^2) 想請問nlog(k/n)怎麼來的? 第六題，有什麼方法可以讓EXTRACT_MID是O(1) 因為我想出來的都是O(n) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 1.174.133.43 ※ 編輯: movo11 來自: 1.174.133.43 (01/17 20:59) ※ 編輯: movo11 來自: 1.174.133.43 (01/17 20:59)
→
01/17 21:17, , 1F
每個pass要搬動n個資料,總共有lg(k/n) Pass
01/17 21:17, 1F
→
01/17 21:19, , 2F
用link list結構就可以讓EXTRACT_MID為O(1)
01/17 21:19, 2F
→
01/18 01:32, , 3F
第二題能再說詳細一下嗎 謝謝
01/18 01:32, 3F
‣ 更多 movo11 的文章
文章代碼(AID): #1Gz_Fyhb (Grad-ProbAsk)