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

[理工] 105交大資演

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

第七大題
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

作者: 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) 沒錯..

繼續閱讀

[共同] 英文交大105 vocabulary第6題viwocm [理工] 105交大資演Denim5566 Re: [理工] [DS] 104台大電機丙 top down insertioneasonc [理工] 105交大計系 leo258x [理工] 105 交大 DS 紅黑樹yaxauw [理工] [DS] 104台大電機丙 top down insertioneasonc Re: [理工] 103台聯大線性代數問題sky2201 Re: [理工] 103台聯大線性代數問題sky2201 [理工] 驅動點阻抗法superdevil [理工] 103台聯大線性代數問題sky2201