1615人气
返回课程 信奥赛CSP-J(真题3)1.5、CSP-J复赛算法运算次数上限估算

在解决复赛的每一道题时,要重点注意数据规模,根据数据规模来采取程序编写策略(算法)。比如:

l如果数据取值范围过大,可能超出int,则果断使用long long;

l如果输入输出的内容过多,果断放弃cin、cout,直接使用scanf、printf;

l根据数据规模来考虑程序应该如何编写(采用的算法是什么)才不会导致某些测试点运行超时(运行超时会丢分),继续向下看。

 

一般来说,信奥赛考试中一道算法题在测试点(测试机)上允许执行的时间为1秒钟,大概也就是能执行1亿行代码。换句话说,测试点上每秒执行10^8次运算基本就是极限了。

所以,对于算法的执行次数,从经验角度来讲给出如下结论供参考:

(1)算法时间复杂度如果为O(1)或者O(logn),基本上不会超时;

(2)算法时间复杂度如果为O(n),那么n不要超过10^8;

(3)算法的时间复杂度如果为O(nlogn),那么n不要超过10^7;

(4)算法的时间复杂度如果为O(n^2),那么n不要超过10^4;

(5)算法的时间复杂度如果为O(n^3),那么n不要超过10^3;

(6)算法的时间复杂度如果为O(2^n),那么n不要超过27(这种算法不建议使用);

(7)算法的时间复杂度如果为O(n!),那么n不要超过11(这种算法不建议使用);

 

一般来说,如果数据规模比较小时,可以使用暴力枚举、递归、深度优先搜索之类的算法,而如果数据规模比较大,一般就要采用递推、二分查找、动态规划之类算法;