作者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/cn.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