是我理解错时间复杂度了吗?

mcqueen @ 2019-08-01 11:16:54

by Polaris_Dane @ 2019-08-01 11:19:51

？？？ 哪里有 n^2啦？？？

by Polaris_Dane @ 2019-08-01 11:20:20

最多nlogn

by mcqueen @ 2019-08-01 11:29:16

@Polaris_Dane
插入的时间复杂度是O(n)
总共有n次操作
所以总的时间复杂度为O(n^2)

by hater @ 2019-08-01 11:35:16

@mcqueen 理论与实际有差距

by hater @ 2019-08-01 11:35:29

很多题目都是这样的

by b2019dy @ 2019-08-01 11:35:47

插入复杂度logn啊

by mcqueen @ 2019-08-01 11:42:34

@b2019dy
二分是logn的，但插入应该是O(n)的

by 樱初音斗橡皮 @ 2019-08-01 11:43:19

@mcqueen 你对vector黑科技的力量一无所知，vector平衡树了解一下

by mcqueen @ 2019-08-01 11:45:38

刚才问了一下同机房的巨佬
他说vector的插入式O(\sqrt n)加上一些玄学的常数。所以数据不是很卡的话就可以卡过去 QWQ

by mcqueen @ 2019-08-01 11:47:48

@樱初音斗橡皮 %%%
蒟蒻连普通平衡树都不会写。您看我名字颜色就知道了QWQ