Evaluación eficiente de esta medida de correlación

Question

¿Cuál crees que sería la forma más eficiente de evaluar la siguiente expresión?

Dada una secuencia binaria $ E_N = (e_1,...,e_N) \in \{ -1,+1 \}^N $ y para $D = (d_1,d_2)$ con enteros no negativos $0 \leq d_1 < d_2 $ .

Evaluar $$\max_{M,D} \lvert \sum_{n = 1}^M e_{n+d_1} e_{n+d_2} \lvert ,$$ donde el máximo se toma sobre todos los $D = (d_1, d_2)$ y $M$ tal que $ 0 \leq d_1 < d_2 < M+d_2 \leq N $

Mi algoritmo parece ser $ O(n^4) $ pero ciertamente podría hacerlo mejor.

Answer 1

Cambiemos ligeramente la definición de su suma:

$$\max_{d_1, d_2, M} \left| \sum_{n=d_1+1}^{d_1+M}e_n e_{n+d_2-d_1}\right|$$

s.t. $d_2-d_1 > 0$ , $1 \le M \le N-d_2$ .

Así que con $\Delta=d_2-d_1$ esto es igual a:

$$\max_{\Delta, l, r} \left| \sum_{n=l}^{r}e_n e_{n+\Delta}\right|$$

s.t. $\Delta > 0$ y $1 \le l \le r \le N-\Delta$ .

Vamos a calcularlo en $\Theta(N^2\log N)$ .

1. Computar $a_{\Delta}(i)=e_i e_{i+\Delta}$ para todos $i, \Delta$ en $\Theta(N^2)$ .
2. Calcular la suma del prefijo $A_{\Delta}(i)=\sum_{k=1}^{i-1}a_{\Delta}(k)$ en $\Theta(N^2)$ . Ahora tienes un oráculo que responde en $\Theta(1)$ a las consultas de la forma "dado $a$ y $b$ ¿Qué es? $\sum_{k=a}^{b}a_{\Delta}(k)$ ?".
3. Inicializar la respuesta a $-\infty$ . Ahora repasa en bucle todos los $\Delta$ y para cada uno de ellos:
   • Insertar inicialmente en alguna estructura de datos $S$ . que permite insertar, eliminar y encontrar el mínimo y el máximo (por ejemplo, dos árboles de búsqueda binarios) todo $A_\Delta(r+1)$ para todos $1 \le r \le N-\Delta$ .
   • Para cada $l$ , encontrar el mínimo $A_\Delta(r+1)$ y el máximo $A_\Delta(r'+1)$ en $S$ . Relaje la respuesta con $|A_{\Delta}(r+1)-A_{\Delta}(l)$ y $|A_\Delta(r'+1)-A_\Delta(l)|$ . Por último, elimine $A_\Delta(l)$ de $S$ .

El $O(\log n)$ Los gastos generales del factor provienen de las operaciones de $S$ que probablemente sean logarítmicas (por ejemplo, si se utilizan BST).

---

En realidad, es posible reducir esta complejidad a $\Theta(n^2)$ sin utilizar ninguna estructura de datos compleja. Notemos que no utilizamos todo el potencial de los BST, porque sólo insertamos elementos en el paso inicial (que es en cierto modo una consulta fuera de línea).

En nuestro algoritmo, sólo necesitamos elementos $A_\Delta(r)$ que son mayores (o menores) que $A_\Delta(s)$ para todos $s>r$ (de lo contrario, el máximo/mínimo no cambiará). El cálculo de esta lista puede realizarse en $\Theta(n)$ . Entonces no necesitamos ningún BST en el tercer paso, sólo actualizar un índice que apunte al elemento máximo/mínimo actual. Cuando se elimina el elemento máximo/mínimo, sólo hay que utilizar la lista construida anteriormente para calcular el siguiente.