[理工] 资结
楼主: shinle14 2019-12-25 10:15:08
想问这题的C错在哪
这页的i 想问错在哪
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，这样也可以吗？