PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Grad-ProbAsk
[理工] 台大105资演
楼主:
ahahahahah
(あああああ)
2018-01-12 19:31:04
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
请问有别的作法吗?
作者: PunchShadow (PunchShadow)
2018-01-13 15:54:00
对 就是有那个性质的红黑树即可网址被截掉了QQ
https://www.ptt.cc/bbs/Grad-ProbAsk/
M.1479362612.A.90A.html上面两行麻烦加在一起xDD
楼主:
ahahahahah
(あああああ)
2018-01-13 14:06:00
谢谢 我研究一下
作者: PunchShadow (PunchShadow)
2018-01-12 19:59:00
2.c 之前版上有人解不同的答案,我也还在困惑
https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.
4.c 就只要满足Smallest height 3 AVL tree即可5.a 我是用Dijkstra 先解出最短path,再带入限制条件把(E,G)、(G,H)换成(E,H)5.a 说错,替换结果应该是(A,D)换(A,B)+(B,D)
作者: a1596482
2018-01-12 21:57:00
5.a 用bellman 做4次?成大复杂度那题我算O(n^4/M)
楼主:
ahahahahah
(あああああ)
2018-01-12 23:36:00
对是Bellman我搞错了XDD
作者:
sarsman
(DeNT15T♠)
2018-01-12 23:37:00
2c 确保root到所有leaf经过的黑node数一样、没有连续两颗红node相连就行1 因为他分割成16个子问题,每个子问题需时theta(1),加总就是16c
继续阅读
[理工] 104台大资工 OS Vectored-I/O
PunchShadow
[理工] 台大资工 99 计系 数题
can18
[理工] 104交大 资演 hashing
qaswed101
[理工] 计组
kobebset105
[理工] proper根轨迹问题
derry20732
[理工] fork
suspend
[理工] 97台大工数C 正交补集问题
poyin0820
[理工] 资工线代 内积 习题
we777
[理工] 102 成大 资演
howard31622
[理工] 清大96计科 复杂度计算
kssdpp222
Links
booklink
Contact Us: admin [ a t ] ucptt.com