1

我正在尝试并行化一些执行一些递归线性方程的软件。我认为其中一些可能会被改编成前缀和。下面是我正在处理的几种方程的几个例子。

标准前缀和定义为：

y[i] = y[i-1] + x[i]

我感兴趣的一个等式看起来像前缀和，但有一个乘法：

y[i] = A*y[i-1] + x[i]

另一个是更深层次的递归：

y[i] = y[i-1] + y[i-2] + x[i]

除了解决这两种变化的方法之外，我想知道是否有资源可以涵盖如何将上述问题调整为前缀和形式。或者更一般地说，采用/调整前缀和以使其更灵活的技术。

4

1 回答 1

1

(1)

y[i] = A*y[i-1] + x[i]

可以写成

y[z] = A^z * y[0] + Sum(A^(z-j) * x[j]) 
    ,where j E [z,1].

A^z * y[0]可以计算在O(log(z))

Sum(A^(z-j) * x[j])中可以计算O(z)。

如果事先知道序列的最大大小（例如max），那么您可以预先计算修改后的前缀和数组x为

prefix_x[i] = A*prefix_x[i-1] + x[i]

     then Sum(A^(z-j) * x[j]) is simply prefix_x[z]
     and the query becomes O(1) with O(max) precomputation.

(2)

y[i] = y[i-1] + y[i-2] + x[i]

可以写成

y[z] = (F[z] * y[1] + F[z-1] * y[0]) + Sum(F[z-j+1] * x[j]) 
    ,where j E [z,2] and F[x] = xth fibonaci number

(F[z] * y[1] + F[z-1] * y[0])可以计算在O(log(z))

Sum(F[z-j+1] * x[j])中可以计算O(z)。

如果事先知道序列的最大大小（例如max），那么您可以预先计算修改后的 x 前缀和数组为

prefix_x[i] = prefix_x[i-1] + prefix_x[i-2] + x[i]

     then Sum(F[z-j+1] * x[j]) is simply prefix_x[z]
     and the query becomes O(1) with O(max) precomputation.
于 2020-04-28T09:14:37.770 回答