减少程序计算大输入所需的时间

Question

下面的代码计算结果的总和(x*k -y) n次，值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

例如，调用带有值的函数，调用(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)

然而，这个实现并不是更好，因为我在计算大数字时会出现错误。

Answer 1

与其寻找一种更快地完成同样的工作的方法，你应该先问一问你是否必须做所有的工作。

基本上您想要计算：

 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 )在数字如此庞大的情况下工作，我们用任意位长进行计算。递归通常会减慢这个过程，因为Python中的函数调用非常昂贵，而且Python没有实现尾调用优化(TCO)。