python之减少程序计算大量输入的时间

下面的代码计算了 n 次结果 (x*k -y) 的总和，k 的值从 1 开始，每次循环运行时递增 1:

def invoke(n,x,y): 
    k=1 
    sum1=0 
    while(n > 0): 
        result=x*k-y  
        k+=1 
        sum1+= result 
        n-=1  
    return sum1 

例如，使用值调用函数 invoke(2,3,5) 会输出 -1，因为对于 k=1，它是 3*1-5 = -2，对于 k=2，它变成3*2-5=1。因此，程序返回 -1，因为同时添加了 -2 和 1。

我遇到的问题是计算大数需要一段时间，有什么办法可以优化这个吗？

为了让它运行得更快，我写了这个程序的递归实现:

def invoke1(n,x,y): 
     k=0 
     if n == 0: 
         return 0 
     else: 
         return x*(k+n)-y + invoke1(n-1,x,y) 

但是，这个实现并没有好多少，因为我在计算大数时出错。

请您参考如下方法:

与其寻找一种更快地完成相同工作的方法，不如问问自己是否必须首先完成所有工作。

基本上你想要计算:

 n 
--- 
\ 
/     x * k - y 
--- 
k=1 

固定了 x 和 y。如果我们对其进行数学分析，我们知道这相当于:

n * (n+1) * x 
-------------  - n * y 
      2 

所以我们可以这样计算:

def invoke(n, x, y): 
    return n * (n+1) * x / 2 - n * y 

或者如果我们只在整数域中执行计算:

def invoke_ints(n, x, y): 
    return n * (n+1) * x // 2 - n * y 

鉴于计算是在常数时间内完成的(如果数字非常大，实际计算通常在 O(log n) 内完成)，时间复杂度是常数，否则，这些是在 O(log n) 中。

迭代和递归函数都在 O(n) 中工作(如果计算在常数时间内)，或者在 O(n log n) 中工作是那么大，我们用任意位长度进行计算。递归通常会减慢该过程，因为 Python 中的函数调用非常昂贵，而且 Python 没有实现尾调用优化 (TCO)。