[理工] 105交大資演

看板Grad-ProbAsk作者 (co)時間8年前 (2016/02/15 11:46), 8年前編輯推噓4(4推 0噓 8→)
留言12則, 5人參與, 最新討論串1/10 (看更多)
第七大題 19小題 http://imgur.com/DQIcOd4
為何C對?? 不是nlogn嗎?? 21小題 http://imgur.com/cKeNaZP
為何A錯??? 第八大題 24小題 http://imgur.com/yJQlhAw
為何B錯??? 第11大題各小題 http://imgur.com/Ka85rEQ
要怎麼做 太變化了看不懂@@ 以上問題 感謝各位大大 對完答案之後... 只能更認命面對後面考試了QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.238.73 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1455507990.A.817.html ※ 編輯: iam30719 (61.230.238.73), 02/15/2016 11:50:19
→
02/15 11:49, , 1F
24. 應該是O(n)吧, 有可能長得很歪
02/15 11:49, 1F
→
02/15 11:51, , 2F
回錯題號是21, 19的話你可以2n個重新用bottom-up建
02/15 11:51, 2F
→
02/15 11:53, , 3F
24. 會至少n log n是因為他是comparison based跟選項說
02/15 11:53, 3F
→
02/15 11:53, , 4F
的無關
02/15 11:53, 4F
→
02/15 12:00, , 5F
21 leftist tree不用balance 可以是skewed tree
02/15 12:00, 5F
感謝兩位 ~~ ※ 編輯: iam30719 (61.230.238.73), 02/15/2016 14:35:52
推
02/15 21:07, , 6F
merge two heaps 應該是 n log n
02/15 21:07, 6F
→
02/15 21:08, , 7F
如果是 O(n) 的話 我就可以得到一個 O(n) 的排序法了..
02/15 21:08, 7F
推
02/15 21:33, , 8F
樓上可以提供參考一下O(n)的排序方法嗎?
02/15 21:33, 8F
→
02/15 21:36, , 9F
merge two heap不是o(n)嗎?
02/15 21:36, 9F
推
02/15 21:53, , 10F
merge two heap就是全部一起bottom up，所以O(n)
02/15 21:53, 10F
推
02/16 00:19, , 11F
我看錯了.. 我以為是把兩個 heap merge 成 sorted list..
02/16 00:19, 11F
→
02/16 00:20, , 12F
所以 merge two heaps 是 O(n) 沒錯..
02/16 00:20, 12F
‣ 更多 iam30719 的文章
文章代碼(AID): #1MmKeMWN (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 1 之 10 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共10篇)
‣ 更多 iam30719 的文章
文章代碼(AID): #1MmKeMWN (Grad-ProbAsk)