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

[movo11 (Larry)]

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)
→ ab170926:每個pass要搬動n個資料,總共有lg(k/n) Pass
→ ab170926:用link list結構就可以讓EXTRACT_MID為O(1)
→ movo11:第二題能再說詳細一下嗎 謝謝