想请教此题
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，是可以省略还是必须写？