[理工] 資結 shinle14 PTT批踢踢實業坊

[理工] 資結

作者: shinle14 2019-12-25 10:15:08

http://i.imgur.com/fgf3uoU.jpg
想問這題的C錯在哪
http://i.imgur.com/yz3KadH.jpg
這頁的i 想問錯在哪
http://i.imgur.com/k9WbyR3.jpg
15的a 答案很像是nlogn，可是調一次rotation次數不是O(1)嗎，n個我覺得是O(n)
15的 f看不太懂想問各位

作者: bochengchen (LFII) 2019-12-25 10:20:00

後面的in order是照大小順序的意思！所以Ｆi錯是因為insertion sort有可能Ｏ(n)完成F前面那句是ＤＰ性質,後面是greedy性質！根本無關a我覺得應該是Ｏ（1)看有沒有其他大大有想法！

作者: FRAXIS (喔喔) 2019-12-25 12:18:00

a 應該是 O(n)Day–Stout–Warren algorithm

作者: bochengchen (LFII) 2019-12-25 13:27:00

感謝Ｆ大！！

作者: mistel (Mistel) 2019-12-25 16:33:00

想問一下，我查到Day–Stout–Warren algorithm是用在平衡BST，但a是問binary tree，這樣也可以嗎？

繼續閱讀

[理工] 105成大資演marvelousbas [理工] 101中央數學ponwar87123 [理工] 演算法eefat [理工] 離散圖論yahooyamgoog [理工] 交大資工台大電機丙計組一些問題mistel [理工] 資工師大北科政大核對答案leegaga61029 [理工] 資演 106交大討論幾題答案ching4562 [理工] 中央101資演ponwar87123 [理工] 107 電機丙資結幾題問題mistel [理工] 102成大資工數學對答案zaqxsw2230