作者jerry900287 ()
看板Grad-ProbAsk
标题[理工] 105/106 台大电机丙 资结
时间Sat Dec 23 23:18:40 2017
请教一下各位大大对於这两题的看法
105 台大电机丙 资结 如图
https://i.imgur.com/5tazIR9.png
这题 有多一个 equal 害我不知道应该是false 还是 true
因为他们 insert 都是 O( n log n )
这题不知道该用实际时间还是用复杂度时间...
还是这题的shorter是指树的高度...?
106 台大电机丙 资结 如图
https://i.imgur.com/1bYNigY.png
这个题目的意思
是有可能建完变成 balanced binary tree 吗?
还是不管怎麽建都是 unbalanced binary tree ?
麻烦各位大大惹
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.243.91.60
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1514042324.A.20A.html
※ 编辑: jerry900287 (111.243.91.60), 12/23/2017 23:19:15
※ 编辑: jerry900287 (111.243.91.60), 12/23/2017 23:20:11
1F：→ winiel559: 觉得第一题是指树高,false(三个点的时候)12/23 23:47
2F：推 FRAXIS: 这些是多选题吗？12/24 06:17
上面是 是非
下面是 多选
※ 编辑: jerry900287 (61.230.131.29), 12/24/2017 09:42:53
3F：推 FRAXIS: 12 abc 都不对 d 是对的 12/24 11:11
4F：→ FRAXIS: e 的话是 O(n) 那题目写 O(n log n) 应该也没错？ 12/24 11:12
5F：推 sarsman: 12.A的机率要怎麽算啊@@ 12/24 11:47
6F：推 FRAXIS: 你只要考虑 n = 2^k - 1 的情况 随机插入变成 perfect 12/24 11:54
7F：→ FRAXIS: balanced search tree 机率非常非常小.. 12/24 11:54
8F：→ kidplayhappy: 12 (b) amortized的情况下为什麽不是O(log n) ? 12/24 12:10
9F：推 FRAXIS: expected 是 O(log n), amortized 应该不会是O(log n) 12/24 12:28
10F：→ FRAXIS: 因为 amortized 是指一连串的 operation 的 worst case 12/24 12:29
11F：→ FRAXIS: 执行时间 随机插入的话 有 > 0 的机率 树会非常不平衡 12/24 12:30
12F：→ FRAXIS: 所以 amortized 没办法是 O(log n) 12/24 12:30
13F：推 s06i06: 第一题我写true,找不到反例，有大大可以找出个反例吗 感 12/24 15:29
14F：→ s06i06: 谢 12/24 15:29
15F：→ kidplayhappy: 如果题目指的是树高，这应该是反例 12/24 16:24
16F：→ kidplayhappy: 如果是执行时间AVL Tree应该会快一些 12/24 16:24
OK 那第一题应该没问题了 谢谢你
18F：推 b10007034: e 为什麽比较紧的upper bound是O(n)？ 12/24 17:54
19F：→ b10007034: 不是直接建一个AVL tree 12/24 17:54
20F：→ b10007034: 给n个data，所以是O（nlogn）吗？ 12/24 17:54
21F：→ b10007034: 顺便问题目的意思，使不平衡变平衡，有这种演算法调整 12/24 17:56
22F：→ b10007034: 吗？类似heap的bottom-up法 12/24 17:56
23F：推 FRAXIS: 先 inorder traverse 把元素存成 sorted array 12/24 20:30
24F：→ FRAXIS: 然後 sorted array 转 balanced tree 12/24 20:30
25F：→ FRAXIS: 这样作会使用额外 O(n) 的空间 不过实际上有其他方法可以 12/24 20:30
26F：→ FRAXIS: O(n) 时间 O(1) 空间把 unbalnaced tree变成balanced tree 12/24 20:31
27F：推 FRAXIS: 可以搜 Day–Stout–Warren algorithm 12/24 20:34
太神 那这样 这题也没问题了 感谢
28F：推 sarsman: 推F大，受益良多XD 12/24 21:36
29F：推 b10007034: 原来如此，又是一个thread bt应用吗 12/25 09:33
30F：→ b10007034: 谢f大，顺便问有些题目出题者的想法，我记得有时候题 12/25 09:35
31F：→ b10007034: 目的upper bound不够紧，答案就会算错 12/25 09:36
32F：→ b10007034: 那像这种时候，这题的e到底可不可以算对呢？还是要写 12/25 09:37
33F：→ b10007034: 老师想看的答案？ 12/25 09:37
34F：推 FRAXIS: 我想除了改考卷的人之外没人可以回答这问题吧.. 12/25 10:31
35F：推 winiel559: 我认为选择题就选对的，计算、简答题才要写tight的 12/25 11:12
36F：→ winiel559: 我认为选择题就选对的，计算、简答题才要写tight的 12/25 11:12
※ 编辑: jerry900287 (60.245.65.177), 12/25/2017 14:19:07
※ 编辑: jerry900287 (60.245.65.177), 12/25/2017 14:38:04
感谢各位陪小弟练剑QQ
※ 编辑: jerry900287 (60.245.65.177), 12/25/2017 14:38:41