1回答

liuyubobobo

2021-03-31

已采纳

基本原则是复杂度乘出来大概是 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 也是可能通过的。但通常不会比这个值更高了。

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

继续加油！：）

0