最后n个数字的加权总和

Question

假设我们正在流中收到数字。收到每个数字后，需要计算最后$ n $数字的加权总和，其中权重始终相同，但任意。

如果允许我们保留数据结构以帮助计算，这可以有效地完成？我们可以做任何比$ theta（n）$更好的，即每次收到一个数字时重新计算总和？

例如：假设权重为$ w = langle w_1，w_2，w_3，w_4 rangle $。在某一时刻，我们有最后的$ n $ numbers $ l_1 = langle a，b，c，d rangle> $，而加权sum $ s_1 = w_1*a+w_2*a+w_2*b+w_3*c+w_4 *D $。

当收到另一个数字$ e $时，我们将列表更新以获取$ l_2 = langle b，c，d，e rangle $，我们需要计算$ s_2 = w_1*b+w_2*c+w_3* D+W_4*E $。

考虑使用FFT通过采用快速傅立叶变换，似乎可以有效地解决此问题的特殊情况。在这里，我们计算了$ n $的倍数的称重总和$ s $。换句话说，我们收到$ n $数字，只有这样，我们才能计算相应的$ n $称重。为此，我们需要$ n-1 $过去的数字（已经计算出来）和$ n $的新数字，总数为$ 2n-1 $。

如果输入数字和权重矢量$ w $的向量定义了多项式$ p（x）$和$ q（x）$的系数，并且系数为$ q $，则我们看到产品$ p（x ） times q（x）$是一个多项式，其系数在$ x^{n-1} $面前，最高$ x^{2n-2} $正是我们寻求的加权总和。可以使用$ theta（n* log（n））$时间的FFT计算这些时间，这使我们平均每个输入号的时间为$θ（ log（n））$时间。

但是，这不是解决问题的解决方案，因为需要有效地计算加权总和 每个 时间收到新数字 - 我们不能延迟计算。

Answer 1

这是对您的方法的阐述。假设随后的$ m $值为零，我们每次$ m $迭代都会使用FFT算法计算时间$ o（n log n）$的$ m $值$ m $值。换句话说，我们正在计算$$ sum_ {i = 0}^{n-1} w_i a_ {t-i+k}， quad 0 leq k leq m-1，$ w_i $ w_i $是$ n $权重（或反向权重），$ a_i $是输入序列，$ t $是当前时间，而$ a_ {t'} = 0 $对于$ t'> t $。

对于以下$ m $迭代，我们能够计算时间$ o（m）$（$ i $ th Iteration需要时间$ o（i）$）中所需的卷积。因此，摊销时间为$ O（m） + O（n log n/m）$。通过选择$ m = sqrt {n log n} $，它可以最大程度地减少这一点，该{n log n} $给出了$ o（ sqrt {n log n}）$的摊销运行时间。

我们可以通过将计算分为多个部分，将其改进为$ o（ sqrt {n log n}）$的最坏情况。修复$ m $，并定义$$ b_ {t，p，o} = sum_ {i = 0}^{m-1} w_ {pm+i} a_ {tm-i+o}， quad c_ { t，p} = b_ {t，p，0}， ldots，b_ {t，p，m-1}。 $$每个$ c_ {t，p} $仅取决于$ 2M $输入，因此可以在时间$ o（m log m）$中计算。另外，给定$ c _ { lfloor t/m rfloor-p，p} $对于$ 0 leq p leq p leq n/m-1 $，我们可以计算时间$ o（n/m + m）$的卷积。因此，计划是维护列表$$ c _ { lfloor t/m rfloor-p，p}， quad 0 leq p leq p leq n/m-1。 $$对于$ m $输入，我们需要更新其中的$ n/m $。每个更新需要时间$ o（m log m）$，因此，如果我们均匀地传播这些更新，每个输入将占用工作$ o（（n/m^2）m log m）= o（（（n/m，） ） log m）$。连同计算卷积本身，每个输入的时间复杂度为$ O（（N/M） Log M + M）$。选择$ m = sqrt {n log n} $，就像以前一样，这给出了$ o（ sqrt {n log n}）$。