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
請問有別的作法嗎？

對 就是有那個性質的紅黑樹即可網址被截掉了QQhttps://www.ptt.cc/bbs/Grad-ProbAsk/M.1479362612.A.90A.html上面兩行麻煩加在一起xDD

謝謝 我研究一下

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)

5.a 用bellman 做4次？成大複雜度那題我算O(n^4/M)

對是Bellman我搞錯了XDD

2c 確保root到所有leaf經過的黑node數一樣、沒有連續兩顆紅node相連就行1 因為他分割成16個子問題，每個子問題需時theta(1)，加總就是16c