[理工] 98 交大資工 DS

看板Grad-ProbAsk作者 (阿渝)時間9年前 (2017/01/09 17:19), 編輯推噓8(8推 0噓 24→)
留言32則, 7人參與, 最新討論串1/1
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
→
01/09 17:22, , 1F
(A)錯在最後一句，lower bound of sorting problem如果
01/09 17:22, 1F
→
01/09 17:22, , 2F
有種既視感（？
01/09 17:22, 2F
→
01/09 17:22, , 3F
不限制在comparison based的話可以到n
01/09 17:22, 3F
→
01/09 17:23, , 4F
(C)錯在No one can win the quick-sort
01/09 17:23, 4F
→
01/09 17:24, , 5F
comparison based裡面insertion跟bubble的best case可
01/09 17:24, 5F
→
01/09 17:24, , 6F
以到O(n)
01/09 17:24, 6F
→
01/09 17:25, , 7F
他們都是錯在不夠嚴謹而已
01/09 17:25, 7F
→
01/09 17:29, , 8F
了解 感謝!
01/09 17:29, 8F
→
01/09 17:32, , 9F
能問一下為什麼不限制在comparison based的話可以到n嗎?
01/09 17:32, 9F
推
01/09 17:37, , 10F
(a)的語義想表達什麼呀，merge sort不是就會使用compari
01/09 17:37, 10F
→
01/09 17:38, , 11F
son了嗎
01/09 17:38, 11F
→
01/09 17:38, , 12F
正想問這個， 我能理解的是merge sort 為 O(nlgn)
01/09 17:38, 12F
推
01/09 17:46, , 13F
A是錯在一個問題的lower bound和一個演算法的lower
01/09 17:46, 13F
→
01/09 17:46, , 14F
bound不一樣，要說一個問題的lower bound是指每個
01/09 17:46, 14F
→
01/09 17:46, , 15F
演算法都至少要nlogn，但是這邊只是merge sort的low
01/09 17:46, 15F
→
01/09 17:46, , 16F
er bound是nlogn
01/09 17:46, 16F
→
01/09 17:52, , 17F
能理解gray大所說的，這樣看好像題目在玩文字遊戲
01/09 17:52, 17F
→
01/09 17:53, , 18F
不限制在comparison就有bucket、radix、counting可以到
01/09 17:53, 18F
→
01/09 17:53, , 19F
O(n)
01/09 17:53, 19F
推
01/09 21:55, , 20F
這兩個選項都是錯在推論方式不對吧
01/09 21:55, 20F
→
01/09 21:55, , 21F
設計出一個 worst case time complexity f(n) 的演算法
01/09 21:55, 21F
→
01/09 21:56, , 22F
並不能證明問題 worst case time complexity的lower bound
01/09 21:56, 22F
推
01/09 22:51, , 23F
不太懂F大你說的，一個演算法在worst case下的lower bou
01/09 22:51, 23F
推
01/09 22:52, , 24F
nd不行代表整個問題的lower bound嗎？
01/09 22:52, 24F
推
01/09 23:10, , 25F
你搞混 問題 與 解法
01/09 23:10, 25F
→
01/09 23:10, , 26F
你提供一個解法 只是代表這問題可以這樣解
01/09 23:10, 26F
→
01/09 23:10, , 27F
不代表沒有更快的解法
01/09 23:10, 27F
→
01/09 23:11, , 28F
所以你證明 merge sort 是 O(n lg n) 不能推論出
01/09 23:11, 28F
→
01/09 23:11, , 29F
sorting problem 的 lower bound 是 n lg n
01/09 23:11, 29F
推
01/09 23:16, , 30F
精確來說 merge sort worst case running time O(n lg n)
01/09 23:16, 30F
→
01/09 23:16, , 31F
只能推論 sorting 問題 worst case upper bound O(n lg n)
01/09 23:16, 31F
推
01/10 23:03, , 32F
我看懂了，感謝
01/10 23:03, 32F
‣ 更多 jch660tw 的文章
文章代碼(AID): #1OSrMlxc (Grad-ProbAsk)