这段代码复杂度 $N\log N$，然后 `push_back`应该也是常数较大的 $O(1)$，所以应该就这么炸掉了
by yummy @ 2021-03-13 11:55:12
（另外这个空间居然还卡进去了
by yummy @ 2021-03-13 11:56:06
@[yummy](/user/101694)
```cpp
int res = 0;
double t1 = clock();
for (int i = 1; i < N; ++i) {
for (int j = i; j < N; j += i)
v[j].push_back(i), res++;
}
double t2 = clock();
for (int i = 1; i <= res; ++i) {
v2.push_back(i);
}
double t3 = clock();
```
两段代码一个1.9s一个0.1s,我太菜了不太懂为啥
by vivaldi @ 2021-03-13 11:59:17
@[vivaldi](/user/275387) 上面的时间复杂度是 $\mathcal{O(n\ln n)}$ 的，下面那份是 $\mathcal{O(n)}$ 的
by Diaоsi @ 2021-03-13 12:05:59
@[Diaоsi](/user/137242)
我那个**res**就是上边的循环次数呀
by vivaldi @ 2021-03-13 12:09:13
v是vector数组
v2是vector
by JRzyh @ 2021-03-13 12:11:13
@[vivaldi](/user/275387) 不好意思没看清楚，或许是因为常数？
by Diaоsi @ 2021-03-13 12:27:05
@[Diaоsi](/user/137242)
经过尝试发现，应该是vector分配空间常数太大了，草
by vivaldi @ 2021-03-13 12:28:58