vector 的 insert 操作时间复杂度究竟是什么级别的，求神犇讲解

P1168 中位数

日奈 @ 2019-09-24 15:45:33

昨天看了某位大佬写的神仙代码，就自己写了写AC过了。

今天机房练习赛出现了类似的题，用这种方法做被骂水过题QAQ

上初赛时老师讲过插入操作是O(n)，但实际这个正解复杂的为O(nlogn)，那这个实际算法O(n^2)应该过不了的，但实际速度却很快

所以insert操作复杂度究竟是多少啊

#include <bits/stdc++.h>
#define cin(x) scanf("%d",&x)
using namespace std;
int n;
vector<int> v;
int main()
{
    cin(n);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin(x);
        v.insert(lower_bound(v.begin(),v.end(),x),x);
        if(i&1)
        {
            printf("%d\n",v[(i-1)/2]);
        }
    }
}

by emptysetvvvv @ 2019-09-24 15:50:11

@日奈

比较快的原因可能是： 1. 数据水； 2. 实际上每次插入，前面的数的下标不用变。

by 日奈 @ 2019-09-24 15:55:30

@lg_emptyset 那应该是数据比较水吧

by 地狱小鬼366 @ 2019-09-24 16:19:40

by Jason__Zhan @ 2019-09-24 16:33:56

vector.insert()跑1e5次在begin()处插入就是能过吧，至少我水平衡树还没有在1e5被卡过（hzw的0.5s时限分块除外）。

by 在想Peach @ 2019-11-14 15:49:54

数据不水也能过，vector利用的memcpy操作非常快，但比1e5更大的数据耗时就会急剧增高，在1e5内的数据操作都是堪比log级的速度

by 林聪 @ 2021-02-24 19:33:59

@日奈

vector+insert，亲测以下数据本机只需要0.7s就可以跑完：

100000

100000 99999 99998 ... 2 1

如果是

100000

1 2 3 ... 99999 100000

甚至只需要0.2s就可以跑完

by lcyxds @ 2021-03-15 09:34:05

P4309 [TJOI2013]最长上升子序列

Code 2 极限全 0 数据洛谷跑 332 ms

by lcyxds @ 2021-03-15 09:47:15

#include <vector>
using namespace std;
int main() {
    vector<char> a;
    for (register int i = 0; i < 837500; i++) a.insert(a.begin(), '\0');
}

这玩意跑5秒整你敢信

by lcyxds @ 2021-03-15 09:47:52

n方过八十万（确信）

|