在解决复赛的每一道题时,要重点注意数据规模,根据数据规模来采取程序编写策略(算法)。比如:
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(这种算法不建议使用);
一般来说,如果数据规模比较小时,可以使用暴力枚举、递归、深度优先搜索之类的算法,而如果数据规模比较大,一般就要采用递推、二分查找、动态规划之类算法;