作者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/m.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