algorithm - 前缀和变化
问题描述
我正在尝试并行化一些执行一些递归线性方程的软件。我认为其中一些可能会被改编成前缀和。下面是我正在处理的几种方程的几个例子。
标准前缀和定义为:
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]
除了解决这两种变化的方法之外,我想知道是否有资源可以涵盖如何将上述问题调整为前缀和形式。或者更一般地说,采用/调整前缀和以使其更灵活的技术。
解决方案
(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.
推荐阅读
- typescript - 打字稿:在命名空间中使用新的
- laravel - 我正在尝试在用户与教育之间建立一对一的关系,但我只从教育表而不是用户中获得结果
- node.js - 为什么 bulkCreate 只在 DB 中写入有限数量的记录(Postgres && Sequelize)
- gradle - 如何将带有参数的现有 Gradle 任务包装到自定义任务中?
- sql - Oracle SQL 从离散数据计算平均/期初/期末余额
- android-automotive - Android Automotives Car API 是否仅适用于 OEM?
- android - MotionLayout 是否支持片段之间的共享元素转换?
- c# - 对角线速度太快
- kubernetes - Bazel Kubernetes 对象错误:没有对象传递给应用(Google 容器注册表)
- angular - 量角器 - 添加等待时间,直到设置 cookie