[理工] 105交大資演 iam30719 PTT批踢踢實業坊

作者: iam30719 (JamWu) 2016-02-15 11:46:28

第七大題
19小題

為何C對?? 不是nlogn嗎??
21小題

為何A錯???
第八大題
24小題

為何B錯???
第11大題各小題

要怎麼做太變化了看不懂@@
以上問題
感謝各位大大
對完答案之後...
只能更認命面對後面考試了QQ

作者: amge1524 (台灣加油) 2016-02-15 11:49:00

24. 應該是O(n)吧, 有可能長得很歪回錯題號是21, 19的話你可以2n個重新用bottom-up建24. 會至少n log n是因為他是comparison based跟選項說的無關

作者: yaxauw (yaxauw) 2016-02-15 12:00:00

21 leftist tree不用balance 可以是skewed tree

作者: FRAXIS (喔喔) 2016-02-15 21:07:00

merge two heaps 應該是 n log n如果是 O(n) 的話我就可以得到一個 O(n) 的排序法了..

作者: amge1524 (台灣加油) 2016-02-15 21:33:00

樓上可以提供參考一下O(n)的排序方法嗎?

作者: prosperous 2016-02-15 21:36:00

merge two heap不是o(n)嗎?

作者: janus7799 (Janus逍遙) 2016-02-15 21:53:00

merge two heap就是全部一起bottom up，所以O(n)

作者: FRAXIS (喔喔) 2016-02-16 00:19:00

我看錯了.. 我以為是把兩個 heap merge 成 sorted list..所以 merge two heaps 是 O(n) 沒錯..

繼續閱讀