怎么看出该题要用时间复杂度为o(n)的算法的？？？？

A_pier @ 2021-10-20 11:00:05

by 良心WA题人 @ 2021-10-20 11:11:05

sort是O(nlogn)的，一般比这个都小很多，不过他想要专门卡你是可以卡地很死，这个数据范围是5\times 10^6，O(n logn)刚好过不了，开O2再卡卡常估计就能过

by 良心WA题人 @ 2021-10-20 11:13:43

不过O2应该也过不了，sort已经是把排序的速度做到近乎极限了。

by sephiloss @ 2021-10-20 11:21:41

一般1000ms内可执行的循环次数大约是10^8这个数量级,sort复杂度是nlogn，n最大的情况下，它需要执行循环的次数大概有

int n=5e6;
printf("%.0lf\n",n*log2(n));

刚好超过了10^8，所以超时。

估算程序的复杂度，将数据范围最值代入，如果超过10^8比较多就会超时

by A_pier @ 2021-10-26 21:41:14

@sephiloss 谢谢谢谢，之前没看见回复（貌似没给我红点提示），今天才看到，谢谢

by A_pier @ 2021-10-26 21:42:07

@良心WA题人 嗯，谢谢，不过大佬没有回答我标题的问题，但还是谢谢

by afowww @ 2021-11-12 23:42:46

一般来说nlogn的算法只能处理刚过百万的数据，但是排序的常数是比较小的，所以可以过好几百万的数据。这个五百万还是有点勉强。考虑到五百万的数据读入量非常大，可以写快读。 手写快排+快读，759ms过了，不写快读要1.2s，就T了