[理工] 98 交大資工 DS

[jch660tw (阿渝)]

http://i.imgur.com/RfAMZug.jpg

請問第三題(A)(C)為什麼錯？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.141.67.176
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1483953583.A.EE6.html
→ yupog2003: (A)錯在最後一句，lower bound of sorting problem如果
→ ken52011219: 有種既視感（？
→ yupog2003: 不限制在comparison based的話可以到n
→ yupog2003: (C)錯在No one can win the quick-sort
→ yupog2003: comparison based裡面insertion跟bubble的best case可
→ yupog2003: 以到O(n)
→ yupog2003: 他們都是錯在不夠嚴謹而已
→ jch660tw: 了解 感謝!
→ m666666m: 能問一下為什麼不限制在comparison based的話可以到n嗎?
推 Transfat: (a)的語義想表達什麼呀，merge sort不是就會使用compari
→ Transfat: son了嗎
→ ken52011219: 正想問這個， 我能理解的是merge sort 為 O(nlgn)
推 gary19941208: A是錯在一個問題的lower bound和一個演算法的lower
→ gary19941208:  bound不一樣，要說一個問題的lower bound是指每個
→ gary19941208: 演算法都至少要nlogn，但是這邊只是merge sort的low
→ gary19941208: er bound是nlogn
→ ken52011219: 能理解gray大所說的，這樣看好像題目在玩文字遊戲
→ yupog2003: 不限制在comparison就有bucket、radix、counting可以到
→ yupog2003: O(n)
推 FRAXIS: 這兩個選項都是錯在推論方式不對吧
→ FRAXIS: 設計出一個 worst case time complexity f(n) 的演算法
→ FRAXIS: 並不能證明問題 worst case time complexity的lower bound
推 Transfat: 不太懂F大你說的，一個演算法在worst case下的lower bou
推 Transfat: nd不行代表整個問題的lower bound嗎？
推 FRAXIS: 你搞混 問題 與 解法
→ FRAXIS: 你提供一個解法 只是代表這問題可以這樣解
→ FRAXIS: 不代表沒有更快的解法
→ FRAXIS: 所以你證明 merge sort 是 O(n lg n) 不能推論出
→ FRAXIS: sorting problem 的 lower bound 是 n lg n
推 FRAXIS: 精確來說 merge sort worst case running time O(n lg n)
→ FRAXIS: 只能推論 sorting 問題 worst case upper bound O(n lg n)
推 Transfat: 我看懂了，感謝