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

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

例如,使用值调用函数,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)

但是,这个实现并没有好多,因为我在计算大数时遇到错误.

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 n),如果数字很大,我们用任意位长度进行计算.递归通常会减慢进程,因为Python中的函数调用非常昂贵,并且Python不实现尾调用优化(TCO).