作者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