作者bmpss92196 (bmpss92196)
看板Grad-ProbAsk
標題[理工] 演算法 複雜度
時間Sat Apr 21 11:36:37 2018
想請教此題
The comparison-based sorting algorithm on n data requires Ω(nlgn) time.
我的理解
根據Ω的意思，此題應該是要證comparison-based sorting 至少(最好情況)nlgn的複雜度
而解答上寫在worst case時至少需要h(樹高)次的比較
再來n個數有n!種可能性的排序，每個葉存一個，至少要有n!個葉
h高度的葉最多為2^h個
我的問題是解答上先說是worst case，但題目不是要最好情況下嗎？
如n=3，a,b,c三數比大小
最好情況不是a>b成立b>c成立 => a>b>c
這樣嗎？
有點不太理解解答的意思，謝謝
另外再請教林立宇老師課本上證明lg(n!)=Θ(nlgn)跟有些題目都沒有取c
定義上是要取c，是可以省略還是必須寫？
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.174.225.79
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1524281800.A.612.html
※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 12:00:58
1F：→ outofyou: 我的理解，requires是考慮最壞情況需要的時間 04/21 12:48
2F：→ outofyou: 加上Ω的意思是，最壞情況至少需要這樣的時間。 04/21 12:49
3F：推 imticba: Ω不一定跟"best case"配對，如果和"worst case"搭配代表 04/21 13:21
4F：→ imticba: 我們想分析worst case下至少要多久時間 04/21 13:21
5F：→ imticba: sorting去分析最好情況比較沒意義，因為最好的狀況可能是 04/21 13:24
6F：→ imticba: 已經排序好的數列，這個狀況底下很多sorting方法會是line 04/21 13:24
7F：→ imticba: ar time 04/21 13:24
8F：→ imticba: 我沒有上林立宇的課，不過推測沒取的意思應該就是等於取c 04/21 13:27
9F：→ imticba: =1 04/21 13:27
感謝兩位大大，懂了
※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 14:34:27