1秒时限情况下算法复杂度要求

挑战程序设计竞赛(第二版)提到:


假设时间限制为1秒的情况下,算法复杂度可行性如下:
10**6 游刃有余
10**7 勉勉强强
10**8 很悬,循环体非常简单才可以


抽签问题 实际测试,的确如此,到10**8 复杂度就要0.3s

以下是n^4算法的测试结果:

>>> 50**4
6250000
0.042s

>>> 100**4
100000000
0.330s

>>> 200**4
1600000000
4.628s


以下是n^2logn算法的测试结果:可以看到 n为200时,复杂度和之前算法n为50的效率一样高

200**2*math.log(200,2)
305754.247590989

0.012s

原文地址:https://www.cnblogs.com/cute/p/14722412.html