首页 > 关于超时的一些说明(我的一些总结)
头像
菜瓜瓜瓜
编辑于 2020-09-07 17:24
+ 关注

关于超时的一些说明(我的一些总结)

楼主参加过一段时间的算法竞赛,被卡过输入输出,知道一些解决办法。
本来以为笔试不会卡输入,没想到真的卡了几次。
现在给大家说一些关于输入超时和复杂度的问题。

先说复杂度:
一般来说1s的题,计算量不能超过1e8(10的8次方),否则就有超时的风险。
例如一个题有1e3的数据,那n^2不会超时,n^3就会超时。
1e6数据情况下,一般n^2超时,nlogn和O(n)都不会超时。

关于卡输入、输出这种。
java的Scanner和System.out.println和c++的cin和cout用的比较多,但其实这两种IO方式都是相对很慢的。在输入量比较大的情况下就会超时。
至于这个“大”有多少呢?大概是1e5-1e6个int这么多吧,牛客的oj应该在5e5左右(所以超过这个就不能用了)

java用有一个BufferReader,PrintWriter,而c++可以用scanf和printf。可以解决这个输入量。
而更大的输入量就需要输入输出挂了(这个一般不会卡,只有算法竞赛会用到)。

以上,希望对大家有帮助。
虽然我笔试也不算很厉害(基本上每次都是差一道题Ak的水平),但是如果大家有什么想问的可以在下面说一下,我会不断更新这个帖子。

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐