作者ahahahahah (Kaneshiro Takeshi)
看板Grad-ProbAsk
标题[理工] 台大105资演
时间Fri Jan 12 19:31:04 2018
1) 时间复杂度
发现跟成大某题一样类型
就直接问这题好了
https://i.imgur.com/iuZWgA7.jpg
https://i.imgur.com/X7ryees.jpg
解答看不太懂
他画的递回树是n^2>M的情况吗？
为什麽第二层是16c
而不是16*c/2=8c
那为什麽n^2<=M的情况就不用管了？
2)
https://i.imgur.com/SdZScFH.jpg
(c)小题
画一个最少结点的AVL Tree
Ok! 但之後要填入红黑树就不太明白了
所以就是随便画
只要符合就好了吗？
例如
https://i.imgur.com/xknYcCW.jpg
还是有规则吗？
3)
https://i.imgur.com/ushGfR4.jpg
https://i.imgur.com/q8dZgAy.jpg
(a)这题应该是要写计算过程吧？
用看的应该拿不到分数？
解法应该是用Floyd-Warshall做4次
可是9*9矩阵好像有点大XD
请问有别的作法吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 49.158.105.145
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1515756667.A.6AB.html
※ 编辑: ahahahahah (49.158.105.145), 01/12/2018 19:33:17
※ 编辑: ahahahahah (49.158.105.145), 01/12/2018 19:35:12
1F：推 PunchShadow: 2.c 之前版上有人解不同的答案，我也还在困惑01/12 19:59
404 not found XDD
3F：→ PunchShadow: 4.c 就只要满足Smallest height 3 AVL tree即可01/12 20:01
不是还要画红黑树
4F：→ PunchShadow: 5.a 我是用Dijkstra 先解出最短path，再带入限制条件01/12 20:03
5F：→ PunchShadow: 把(E,G)、(G,H)换成(E,H)01/12 20:04
6F：→ PunchShadow: 5.a 说错，替换结果应该是(A,D)换(A,B)+(B,D)01/12 20:21
※ 编辑: ahahahahah (49.158.105.145), 01/12/2018 21:03:26
7F：推 a1596482: 5.a 用bellman 做4次？ 01/12 21:57
8F：推 a1596482: 成大复杂度那题我算O(n^4/M) 01/12 22:00
9F：→ ahahahahah: 对是Bellman我搞错了XDD 01/12 23:36
10F：→ sarsman: 2c 确保root到所有leaf经过的黑node数一样、没有连续两颗 01/12 23:37
11F：→ sarsman: 红node相连就行 01/12 23:37
12F：→ sarsman: 1 因为他分割成16个子问题，每个子问题需时theta(1)，加 01/13 00:00
13F：→ sarsman: 总就是16c 01/13 00:00
14F：→ ahahahahah: 谢谢 我研究一下 01/13 14:06
15F：推 PunchShadow: 对 就是有那个性质的红黑树即可 01/13 15:54
16F：→ PunchShadow: 网址被截掉了QQ 01/13 15:54
18F：→ PunchShadow: M.1479362612.A.90A.html 01/13 15:55
19F：→ PunchShadow: 上面两行麻烦加在一起xDD 01/13 15:55