作者IDontBite (IDontBite)
看板Grad-ProbAsk
标题[理工] [资结]-93成大电机丁
时间Wed Jan 27 16:31:14 2010
Which is(are) true for heap sort?
(A) an unstable sorting algorithm
(B) comparison-based sorting algorithm
(C) time complexity O(logn)
(D) time complexity omega(n)
(E) space complexity O(nlogn)
(F) None above
洪逸本解答: A.B
关於D.E有点不同看法,
(D) T(n) = theta(nlogn) = omega(n)
(E) S(n) = theta(1) = O(nlogn)
感觉并不冲突, 请问哪个才对呢?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.32.189.59
1F：推 qazwsxee:距离差太远了~虽然定义上是包含在里面~但不可以这样写 01/27 16:39
2F：→ qazwsxee:不然我每题都写~omega(1)~超厉害~0 MISS!所有位置都包含 01/27 16:42
3F：→ qazwsxee:写O(n^10)，n^9到nlogn到n到1都有，教授会给我对吗? 01/27 16:46
4F：推 FRAXIS:楼上你说的是填充或是证明题 你这样写是正确的结果 01/27 17:21
5F：→ FRAXIS:但是不够tight，题目多半都会要求证明一个tight bound 01/27 17:22
6F：→ FRAXIS:教授可以依此来扣分.. 01/27 17:22
7F：→ FRAXIS:这题是选择题，搞不好教授就是要考细心和观念清不清楚.. 01/27 17:22
8F：推 qazwsxee:我觉得有够暗黑..."搞不好" <= 这我可不敢赌 01/27 18:08
9F：→ qazwsxee:有准确逼近的值不问~却要取这种不逼近的值来问你~ 01/27 18:11
10F：→ qazwsxee:教授敢这样给对~肯定很多人都会答错~成长函数怎麽可能可 01/27 18:13
11F：→ qazwsxee:以不准确逼近~n^2与nlogn与n，成长後数值差得远了 01/27 18:16
12F：→ qazwsxee:我觉得:成长函数若没 准确逼近(合理+有意义)，就是错了。 01/27 18:25
13F：推 dendrobium:以omega定义来说 其实D是对的 01/27 22:53
14F：→ dendrobium: E 的话应该是 O(1) 吧 01/27 22:54
15F：推 FRAXIS:O(nlogn) 包含 O(1) 所以从定义上看E也没问题 01/28 09:26