[理工] 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