[理工] 105交大 資演

[ex8338 (三十八)]

 Merge sort is divide and conquer approach and the time required
is modeld by T(n)=2T(n/2)+⊙(n).
Sloving T(n),we get ⊙(nlogn).Thus merge sort needs at least nlogn time.

請問這句話錯在哪?
at least 嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.187.43.206
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483691024.A.AB9.html
推 moooner: 我也有疑問XD
→ ken52011219: at least 吧，代表它上界無限制 (?
→ ken52011219: 好像是 O(nlogn)
推 Transfat: 還是他想表達的是time complexity不能代表時間，只能說
→ Transfat: 是一個時間的bounds?
→ w181496: 這題我也覺得怪 感覺在玩文字遊戲..
→ yupog2003: 我的看法同T大，原式應該是T(n)=2T(n/2)+n/2
→ yupog2003: 所以他的model是對的，但是推導出來應該是
→ yupog2003: (n/2)*log_2(n)，雖然也是theta(nlogn)，可是拿來說
→ yupog2003: 執行時間就不太恰當了
→ yupog2003: 不負責任推估，搞不好他說at most就對了，因為
→ yupog2003: nlogn > (n/2)logn
推 s89162504: 這題送分了 應該不用鑽這個牛角尖啦
→ yupog2003: 原來如此XD