ACM中算法时间约束
ACM中算法时间约束
一般ACM竞赛C/C++的时间限制是一秒，因此可以根据题目数据来推断该题所使用的算法。
算法的时间复杂度在 1 0 7 10^7 107左右合适，最多不能超过 1 0 8 10^8 108， O ( n ) O(n) O(n)的极限就在 1 0 8 10^8 108左右。
| 问题规模n | O ( l o g n ) O(logn) O(logn) | O ( n ) O(n) O(n) | O ( n l o g n ) O(nlogn) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( n 3 ) O(n^3) O(n3) | O ( 2 n ) O(2^n) O(2n) | O ( n ! ) O(n!) O(n!) |
|---|---|---|---|---|---|---|---|
| n < 11 n<11 n<11 | √ | √ | √ | √ | √ | √ | √ |
| n < 25 n<25 n<25 | √ | √ | √ | √ | √ | √ | × |
| n < 300 n<300 n<300 | √ | √ | √ | √ | √ | × | × |
| n < 5000 n<5000 n<5000 | √ | √ | √ | √ | × | × | × |
| n < 1 0 6 n<10^6 n<106 | √ | √ | √ | × | × | × | × |
| n < 1 0 7 n<10^7 n<107 | √ | √ | × | × | × | × | × |
| n > 1 0 8 n>10^8 n>108 | √ | × | × | × | × | × | × |