[理工] [資結]-成大93-電機丁

看板Grad-ProbAsk作者 (IDontBite)時間16年前 (2010/01/27 16:31), 編輯推噓5(5推 0噓 10→)
留言15則, 3人參與, 最新討論串1/2 (看更多)
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
推
01/27 16:39, , 1F
距離差太遠了~雖然定義上是包含在裡面~但不可以這樣寫
01/27 16:39, 1F
→
01/27 16:42, , 2F
不然我每題都寫~omega(1)~超厲害~0 MISS!所有位置都包含
01/27 16:42, 2F
→
01/27 16:46, , 3F
寫O(n^10)，n^9到nlogn到n到1都有，教授會給我對嗎?
01/27 16:46, 3F
推
01/27 17:21, , 4F
樓上你說的是填充或是證明題 你這樣寫是正確的結果
01/27 17:21, 4F
→
01/27 17:22, , 5F
但是不夠tight，題目多半都會要求證明一個tight bound
01/27 17:22, 5F
→
01/27 17:22, , 6F
教授可以依此來扣分..
01/27 17:22, 6F
→
01/27 17:22, , 7F
這題是選擇題，搞不好教授就是要考細心和觀念清不清楚..
01/27 17:22, 7F
推
01/27 18:08, , 8F
我覺得有夠暗黑..."搞不好" <= 這我可不敢賭
01/27 18:08, 8F
→
01/27 18:11, , 9F
有準確逼近的值不問~卻要取這種不逼近的值來問你~
01/27 18:11, 9F
→
01/27 18:13, , 10F
教授敢這樣給對~肯定很多人都會答錯~成長函數怎麼可能可
01/27 18:13, 10F
→
01/27 18:16, , 11F
以不準確逼近~n^2與nlogn與n，成長後數值差得遠了
01/27 18:16, 11F
→
01/27 18:25, , 12F
我覺得:成長函數若沒 準確逼近(合理+有意義)，就是錯了。
01/27 18:25, 12F
推
01/27 22:53, , 13F
以omega定義來說 其實D是對的
01/27 22:53, 13F
→
01/27 22:54, , 14F
E 的話應該是 O(1) 吧
01/27 22:54, 14F
推
01/28 09:26, , 15F
O(nlogn) 包含 O(1) 所以從定義上看E也沒問題
01/28 09:26, 15F
‣ 更多 IDontBite 的文章
文章代碼(AID): #1BN_dLVf (Grad-ProbAsk)
‣ 更多 IDontBite 的文章
文章代碼(AID): #1BN_dLVf (Grad-ProbAsk)