Problema de árbol de secuencia recursiva (investigaciones originales en el campo de la ciencia comp.)

Question

Esta pregunta aparece también en http://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. Me dijeron que el cross-posting en esta situación en particular podría ser aprobado, ya que la pregunta puede ser visto desde muchos ángulos.

Soy un investigador en el campo de las ciencias de la computación. En mi investigación, tengo el siguiente problema, que he estado pensando durante bastante tiempo ahora.

Creo que el problema se explica mejor a través de un ejemplo, así que primero asumir este tipo de estructura de árbol:

 1, 2, 3, 4, 5, 6, 7, 8
 / \
 6, 8, 10, 12 -4, -4, -4, -4
 / \ / \ 
 16, 20 -4, -4 -8, -8, 0, 0
 / \ / \ / \ / \
36 -4 -8 0 -16 0 0 0

La raíz del árbol es siempre una cierta secuencia $s = (s_0, ..., s_{N-1})$ donde $N = 2^p$ algunos $p \in \mathbb{N}, p>2$. Por favor, tenga en cuenta que estoy en busca de una solución general a este, no sólo para las secuencias de la forma $1, 2, ..., 2^p$. Como se puede ver, el árbol se define de una manera recursiva: el de la izquierda nodo está dada por

$left(k)=root(k)+root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$

y el derecho nodo

$right(k)=root(k)-root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$

Así, por ejemplo, (6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8) y (-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7) daría el segundo nivel del árbol.

Estoy interesado sólo en el nivel más bajo del árbol, es decir, la secuencia de (36, -4, -8, 0, -16, 0, 0, 0). Si, calculo que el árbol de forma recursiva, la complejidad computacional se $O(N log N)$. Que es un poco lento para el propósito del algoritmo. Es posible calcular el último nivel en el tiempo lineal?

Si un lineales en tiempo del algoritmo es posible, y a encontrar, voy a agregar como un autor en el papel el algoritmo aparecerá en. El problema que constituye alrededor de 1/10 de la idea/contenido en el papel.

Si un lineales en tiempo del algoritmo no es posible, probablemente voy a tener que reconsiderar otras partes del papel, y dejar esto totalmente. En tal caso, todavía puedo reconocer sus esfuerzos en los agradecimientos. (O, si la solución es una contribución de muchas personas, me podría crédito de toda la matemática SE de la comunidad.)

Answer 1

Como otros han señalado, la transformación que está pidiendo se llama la transformación de Hadamard (esencialmente funciona como una transformada discreta de Fourier). Mientras que la multiplicación de la matriz "trivial" $O(n^2)$ tiempo, la estructura de la matriz permite el cómputo en $O(n\log n)$ tiempo. Sin embargo, es menos como que esto puede acelerarse más, ya podría implicar un salto más rápido de la FFT, que es un problema abierto importante.

Answer 2

Para el caso de que $p=3$ y una secuencia arbitraria $(s_{1},...,s_{8})$ I construyó la matriz: $M=\begin{bmatrix} 1& 1& 1& 1& 1& 1& 1& 1\\ 1&-1& 1&-1& 1&-1& 1&-1\\ 1& 1&-1&-1& 1& 1&-1&-1\\ 1&-1&-1& 1& 1&-1&-1& 1\\ 1& 1& 1& 1&-1&-1&-1&-1\\ 1&-1& 1&-1&-1& 1&-1& 1\\ 1& 1&-1&-1&-1&-1& 1& 1\\ 1&-1&-1& 1&-1& 1& 1&-1\\ \end{bmatrix}$ Such that the $i^{th}$ leaf: $L_{i}=\sum^{N}_{j=1}s_{j}M[i,j]$

Estúpidamente implementado (suponiendo que $M$ puede ser construido de forma gratuita!) esto llevaría $O(n^{2})$ del tiempo. Por supuesto, en el cómputo de estas sumas de trabajo puede ser guardado: por ejemplo

$L_{1}=\sum^{N}_{i=1}s_{i}$ y $L_{\frac{N}{2}+1}=\sum^{\frac{N}{2}}_{i=1}s_{i}-\sum^{N}_{i=\frac{N} {2}+1}s_{i}$

Si se calculan las dos sumatorias en $L_{\frac{N}{2}+1}$ por separado podemos combinarlos en dos soluciones, $L_{1}$$L_{\frac{N}{2}+1}$, en tiempo constante. Sin embargo es mi intuición de que un divide y vencerás estrategia de modelado en este tipo de técnicas no serían capaces de mejorar en el que ya se observan enlazado de $O(N log(N))$.

Yo creo que si no es explotable estructura de la raíz de la secuencia, a continuación, la definición recursiva que proponemos es asintóticamente óptimo. (Voy a mirar en una forma de demostrar esta afirmación.)

Answer 3

El $n$th (contando desde $1$) término del nivel más bajo del árbol con la raíz de $1..2^p$ es:

$n=1$: $ \ \ \ \ \ \ \ 2^{k-1}(2^k+1) $
cual es el $2^k$ésimo número triangular, porque cuando la rama izquierda es seguida de la suma de todos los números en cada nodo se reunió permanece constante.

$n=2^i+1$: $\ \ \ \ \ \ \ 2^{k+i-1} $
La primera vez que una rama derecha, el constante secuencia $-2^{n-1}...-2^{n-1}$ se produce, y siempre siguiendo la rama izquierda después de que se duplica cada término.

$0$
para otros $n$ porque la toma de la rama derecha una vez que se da una constante de la secuencia, y una secuencia de ceros la próxima vez que la rama derecha de la toma.

Answer 4

Esto es más de un comentario, pero es demasiado grande para el bloque de comentario. Una interesante nota sobre Kaya de la matriz $\mathbf{M}$: creo que se puede definir de forma recursiva para cualquier valor de $p$. (Debo señalar aquí que este es mi creencia. Todavía tengo que probarlo...)

Es decir, que $\mathbf{M}_p$ ser la matriz para el valor de $p$ (aquí, vamos a quitar el límite en $p\gt2$).

Deje $\mathbf{M}_1 = \begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$.

A continuación,$\mathbf{M}_n = \begin{pmatrix} \mathbf{M}_{n-1} & \mathbf{M}_{n-1} \\ \mathbf{M}_{n-1} & -\mathbf{M}_{n-1}\end{pmatrix}$.

Ah Ja! Gracias a algunas de las búsquedas basadas fuera de Suresh Venkat la respuesta, me encontré con que esta matriz se llama el Walsh de la Matriz. Multiplicar esta matriz por un vector columna de su primera secuencia proporciona un vector columna de la parte inferior de la secuencia.

Como una nota del lado, esto hace casi un fractal patrón similar al color. :)
El de arriba es para $p=4$.

EDIT: estoy casi seguro de que he visto una gráfica similar a la de arriba antes. Si alguien reconoce algo similar, eso sería genial...