如何预测非线性脚本的运行时间？

Question

我用python编写了这个简单的代码来计算给定数量的素数。在

我想问的问题是，我是否可以编写一个脚本来计算在处理器周期方面，执行这个脚本需要多长时间？如果是，那怎么办？在

primes = [2]
pstep = 3
count = 1

def ifprime (a):

""" Checking if the passed number is prime or not"""
global primes

for check in primes:
    if (a%check) == 0:
            return False
return True

while 1000000000>= count:

if ifprime(pstep):
    primes.append (pstep)
    print pstep
    count += 1
pstep += 1

这个问题的有趣之处在于，在x个循环的递增之后，我是否找到素数几乎是不可能预测的。此外，在这种情况下会发生递归，因为“prime”列表越大，执行此函数所需的时间就越长。在

有什么提示吗？在

Answer 1

好吧，如果你在linux上，你可以使用'time'命令，然后解析它的结果。在

对于你的问题，我会为1000个不同大小的大素数做计时，然后画一个图表，这样就很容易分析了。在

Answer 2

我认为你必须使用素数分布的近似值，la PNT，它（我认为）表明在1和x之间，你将有大约x/ln(x)素数（ln是自然对数）。因此，给定单个迭代所需时间的粗略估计，您应该能够创建一个估计值。在

你的列表中有大约x/ln（x）素数。您的主代码块（在while循环内）具有恒定的时间（有效地）…因此：

t（x）~x/ln（x）*a+b+t（x-1）

其中t(x)是迭代x（包括x）所用的时间，a是检查列表中每个素数所用的时间（模运算），b是主循环的“常量”时间。我隐约记得有一种方法可以把这种递归函数转换成线性函数；）

Answer 3

如果您想预测任意进程在完成之前所需的时间，那么您不能这样做，因为这基本上就是Halting Problem背后的问题。在特殊情况下，您可以估计脚本将花费的时间，例如，如果您知道它是以不允许循环的方式生成的。在

在寻找素数的特殊情况下，更难猜测在运行该过程之前所需的时间，因为只有一个间隔内素数的下限，但这无助于找到它们。在