[理工] 演算法 複雜度

[bmpss92196 (bmpss92196)]

想請教此題
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1524281800.A.612.html
※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 12:00:58
→ outofyou: 我的理解，requires是考慮最壞情況需要的時間
→ outofyou: 加上Ω的意思是，最壞情況至少需要這樣的時間。
推 imticba: Ω不一定跟"best case"配對，如果和"worst case"搭配代表
→ imticba: 我們想分析worst case下至少要多久時間
→ imticba: sorting去分析最好情況比較沒意義，因為最好的狀況可能是
→ imticba: 已經排序好的數列，這個狀況底下很多sorting方法會是line
→ imticba: ar time
→ imticba: 我沒有上林立宇的課，不過推測沒取的意思應該就是等於取c
→ imticba: =1
感謝兩位大大，懂了
※ 編輯: bmpss92196 (1.174.225.79), 04/21/2018 14:34:27