1回答

liuyubobobo

2021-07-27

如果数据规模是 n^4，那么 O(n^2) 算法需要的操作数量，就达到了 10^8 这个量级。整体上 10^8 的规模在一般 OJ 上 1 s 内通过是有风险的。虽然不排除剪枝或者语言优化或者编译上的一些其他原因使得这个量级能通过。

但如果数据规模是 5 * 10^4，乘出来是 25 * 10^8，1 s 一定无法通过。

基本原则是复杂度乘出来大概是 10^6-10^7 左右，肯定可以通过。

比如一个问题，数据规模是 10^6-10^7，基本上就是要设计一个 O(n) 的算法。（当然 O(logn) 也可以，也就是更优复杂度也可以。下同。）

如果一个问题，数据规模是 10^5，O(nlogn) 的算法就没有问题。因为 log(10^5) < 20，就算取 20，nlogn 大概是 2*10^6。

如果一个问题，数据规模是 10^4，O(nsqrt(n)) 的算法就没问题，此时 nsqrt(n) = 10^6；

如果一个问题，数据规模是 10^3，O(n^2) 的算法就没问题，此时 n^2 = 10^6；

如果一个问题，数据规模是 10^2，O(n^3) 的算法就没问题，此时 n^3 = 10^6；

如果一个问题，数据规模是 20,，此时，O(2^n) 的算法就没问题，此时，2^n 大概是 10^6。

这是对绝大多数 OJ 的经验值，大体问题不大。也不排除一些 OJ 的一些问题，时间可以到达 5s（而非 1s），此时，乘出来大概是 10^8 也是可能通过的。但通常不会比这个值更高了。

另外，对于一些问题，可能虽然理论复杂度很高，但可以优化的特别狠（但优化无法降低最低复杂度），此时也可能突破这个值。但这些都属于特殊情况，玩儿竞赛玩儿到一定程度可以在考虑这些情况，这些不是普遍情况。（通常也不是考虑出来的，见多了慢慢就了解了）。

所以，个数据规模基本上就是在限制你使用更差的算法能通过的可能性。

继续加油！：）

1

0