Supongamos que estamos recibiendo números en una secuencia. Después de recibir cada número, se debe calcular una suma ponderada de los últimos números, donde los pesos son siempre los mismos, pero arbitrarios.
¿Cuán eficiente puede hacerse esto si se nos permite mantener una estructura de datos para ayudar con el cálculo? ¿Podemos hacer algo mejor que , es decir, volver a calcular la suma cada vez que se recibe un número?
Por ejemplo: Supongamos que los pesos son . En un momento tenemos la lista de los últimos números , y la suma ponderada .
Cuando otro número, es recibido,, actualizamos la lista para obtener y tenemos que calcular .
Consideración usando FFT Un caso especial de este problema parece resolverse eficientemente empleando la Transformada Rápida de Fourier. Aquí, calculamos las sumas pesadas en múltiplos de . En otras palabras, recibimos números y solo entonces podemos calcular las sumas pesadas correspondientes . Para hacer esto, necesitamos números pasados (para los cuales ya se han calculado sumas), y nuevos números, en total números.
Si este vector de números de entrada y el vector de peso definen los coeficientes de los polinomios y , con los coeficientes en invertidos, vemos que el producto es un polinomio cuyos coeficientes delante de hasta son exactamente las sumas ponderadas que buscamos. Estos se pueden calcular utilizando FFT en tiempo, que nos da un promedio detiempo por número de entrada.
Sin embargo, esta no es una solución al problema como se indicó, porque se requiere que la suma ponderada se calcule eficientemente cada vez que se recibe un nuevo número; no podemos retrasar el cálculo.
fuente
Respuestas:
Aquí hay una elaboración de su enfoque. Cada iteraciones, utilizamos el algoritmo FFT para calcular los valores de la convolución en el tiempo , suponiendo que los valores subsiguientes sean cero. En otras palabras, estamos calculando donde son los pesos (o los pesos inversos), es la secuencia de entrada, es la hora actual y para .m O ( n log n ) m n - 1 ∑ i = 0 w i a t - i + k ,m m O(nlogn) m w i n a i t a t ′ = 0 t ′ > t
Para cada uno de los siguientes iteraciones, somos capaces de calcular la convolución requerida en el tiempo (el ésimo iteración necesita tiempo ). Entonces el tiempo amortizado es . Esto se minimiza eligiendo , que proporciona un tiempo de ejecución amortizado de .m O(m) i O(i) O(m)+O(nlogn/m) m=nlogn−−−−−√ O(nlogn−−−−−√)
Podemos mejorar esto al peor tiempo de ejecución de dividiendo el cálculo en partes. Arregle , y defina Cada depende solo de entradas de , por lo que se puede calcular en el tiempo . Además, dado para , podemos calcular la convolución en el tiempo . Por lo tanto, el plan es mantener la lista Para cada período deO(nlogn−−−−−√) m
fuente