最後の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> $、および加重合計$ s_1 = w_1*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））$ timeのfftを使用して計算できます。

ただし、これは、加重合計が効率的に計算される必要があるため、述べたように問題の解決策ではありません 各 新しい番号が受信される時間 - 計算を遅らせることはできません。

Answer 1

これがあなたのアプローチの詳細です。 $ m $ iterationsごとに、FFTアルゴリズムを使用して、後続の$ m $値がゼロであると仮定して、時間$ o（n log n）$の畳み込みの$ m $値を計算します。言い換えれば、私たちは$$ sum_ {i = 0}^{n-1} w_i a_ {t-i+k}、 quad 0 leq k leq m-1、$$ where $ w_i $を計算しています$ n $ weights（または逆重み）、$ a_i $は入力シーケンス、$ t $は現在の時刻、$ a_ {t '} = 0 $ for $ t'> t $です。

次の$ m $ iterationsのそれぞれについて、時間の$ o（m）$の必要な畳み込みを計算することができます（$ i $ iterationには時間$ o（i）$）が必要です。したがって、償却時間は$ o（m） + o（n log n/m）$です。これは、$ m = 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、m-1}。各$ c_ {t、p} $は、$ 200万の入力のみに依存するため、時間で計算できます$ o（m log m）$。また、$ c _ { lfloor t/m rfloor-p、p} $が$ 0 leq p leq n/m-1 $の場合、時間の畳み込みを計算できます$ o（n/m + m）$ 。したがって、計画は、リストを維持することです$$ c _ { lfloor t/m rfloor-p、p}、 quad 0 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}）$を与えます。