时间复杂度估算（OI信息学奥赛）

来源：百度知道 编辑：UC知道 时间：2024/06/17 17:47:12
如何进行时间复杂度的估算呢？奥赛中要求1秒钟出结果，那么当复杂度为
n^2,n^3,nlogn,n!,2^n,对应的n应该是多少？

上星期在某网站看到过的，结果忘了。

一般来说，10^6的程序可以稳过。
也就是说，
当n=1000时，一般就要用O(n^2)的算法
当n=100时，一半就要用O(n^3)的算法
当n=10^4或10^5时，一般是O(nlogn)的算法
当n是一个很小的数据的时候，可以考虑n!或2^n

如果你的复杂度算出来是10^7或10^8，如果算法简单的话（常数小）可能可以过，如果常数很大就玄了。

大体就是这样吧

这个你应该去看看这方面的书！