Mostrar que las consultas de suma de intervalo en una matriz binaria no se pueden hacer usando espacio lineal y tiempo constante

Se le da una matriz binaria de tamaño . $n$

Quiero mostrar que ningún algoritmo puede hacer lo siguiente (o sorprenderse y descubrir que estos algoritmos existen después de todo):

1) Preprocese la matriz de entrada con tiempo ilimitado, pero solo con bits . $O(n)$

2) Responda consultas en tiempo constante, donde la consulta solicita el número de bits establecidos entre el índice y el índice en la matriz. $(x,y)$ $x$ $y$

Parece que el tiempo constante por consulta no debería permitir que el algoritmo lea suficiente información para calcular el número de bits establecidos.

¿Cómo podemos demostrar que no existe tal algoritmo?

Una pregunta más general sería:

dado que el algoritmo puede usar el espacio , ¿qué límite inferior en el tiempo de consulta podemos derivar? $f(n)$

Obviamente, si tenemos un espacio podemos almacenar todas las sumas parciales y responder consultas en , pero ¿y si es más pequeño? $f=\Omega(n\log n)$ $O(1)$ $f$

Puede suponer que el tamaño de una palabra de memoria es y podemos leer los índices en tiempo constante. $\Theta(\log n)$ $x,y$

@ EmilJeřábek - Quiero que el algoritmo use bits

(lineales en el tamaño de entrada), no palabras de memoria

. ¿Tiene sentido?

O (n)

$O(n)$

O (n)

$O(n)$

Ya veo, gracias por la aclaración. Ahora, otra pregunta: ¿qué operaciones puedes hacer en tiempo constante en palabras de memoria? Aquí hay un algoritmo candidato: dividir la matriz en bloques de tamaño

, y para cada bloque

, almacenar el contenido de

como una palabra, y el recuento de bits establecidos antes de

como otra palabra. Esto hace

bits. Cada consulta se puede responder mediante el examen de cuatro palabras, y se puede calcular utilizando operaciones

en estas palabras, tales como turnos, sustracción y (lo más importante) recuento de población. ¿Su modelo permite esto?

(\log n)

$(\log n)$

b

$b$

b

$b$

b

$b$

O (n)

$O(n)$

O (1)

$O(1)$

Emil Jeřábek

@ EmilJeřábek - Solo tenía en mente operaciones aritméticas, indexación y búsquedas de bits (es decir, buscar un bit específico de una palabra). También se pueden considerar operaciones de bits estándar, como los desplazamientos Estoy de acuerdo en que si pudiéramos contar el número de bits establecidos en

, su algoritmo realmente resuelve el problema.

O (1)

$O(1)$

El problema proviene de un algoritmo que estamos creando para consultas de suma de intervalos sobre ventanas deslizantes. Es decir, tenemos una secuencia de enteros, cada uno en

y deseamos aproximar la suma de un intervalo dado. Nuestro problema se reduce al recuento exacto de intervalos en una matriz binaria (mucho más pequeña) (que también se `` desliza ''). Para una ventana deslizante binaria de tamaño

, utilizamos

bits, agregamos un bit en tiempo constante amortizado y realizamos consultas en

. Me preguntaba si las consultas de tiempo constante son factibles, incluso si la matriz no se actualiza.

0, 1, \dots, R

${0,1,\ldots, R}$

n

$n$

O (n)

$O(n)$

O (\log n)

$O(\log n)$

@ EmilJeřábek: ¡gracias por su sugerencia y análisis! Esta puede ser una respuesta a la pregunta, a pesar de que no responde completamente a nuestras necesidades. El espacio de bits

es una restricción difícil para nosotros, y deseamos demostrar que ningún algoritmo puede responder consultas en tiempo constante.

O (n)

$O(n)$

Respuestas:

Creo que lo que está buscando es una estructura de datos compacta que respalde la operación de clasificación. Ver...

https://en.m.wikipedia.org/wiki/Succinct_data_structure

Específicamente, puede modificar la solución Emils (primera) para eliminar la operación de conteo emergente y reemplazarla con una tabla de búsqueda (para más detalles, consulte el artículo wiki). Al reducir el tamaño de un bloque a (log n) / 2 bits, la tabla de búsqueda utiliza o (n) bits.

Benjamin Sach
fuente

(* facepalm *) Tabla de búsqueda, obviamente. ¿Por qué no pensé en eso?

Emil Jeřábek

En vista del comentario del OP anterior, vale la pena señalar que la estructura se puede implementar fácilmente como una ventana deslizante, por lo que mover la ventana un bit (o incluso bloquear) también lleva tiempo constante.

Emil Jeřábek

@ EmilJeřábek: traducir su solución a la configuración de la ventana deslizante no es sencillo. En lugar de contar el número de bits establecidos en toda la parte de la matriz que precede al bloque actual, necesitamos contar el número de bits establecidos dentro de la ventana deslizante que precede a este bloque, que no parece factible en un tiempo constante. ¿Me estoy perdiendo algo?

x

$x$

y

$y$

n

$n$

$\log n$ $\log_2n$ $\log^{(k)}n$ $\mathop{\underbrace{\log\dots\log}_{k\text{ times}}}n$ $\log^*n$ $\tilde O(t(n))$ $O(t(n)\operatorname{polylog}(t(n)))$

Propuesta: Hay algoritmos que logran

$O(n\log^{(k)}n)$ $O(1)$ $k$

$O(n)$ $\tilde O(\log^*n)$

$k>0$ $n=b_0>b_1>\dots>b_k>0$ $n$ $b_0$ $b_1$ $b_2$ $k$ $b_i$ $2$

$i=1,\dots,k$ $i$ $(i-1)$
$k$ $k$ $x$ $y$

$b_i$

n \sum_{i = 1}^{k} \frac{\log b_{i - 1}}{b_{i}},

$n\sum_{i=1}^k\frac{\log b_{i-1}}{b_i},$

O (k + b_{k}) .

$O(k+b_k).$

$k$ $b_i=\log^{(i)}n$ $0<i<k$ $b_k=1$

$k=\log^*n$

b_{i} = i (\log i)^{3} \log^{(i)} n .

$b_i=i(\log i)^3\log^{(i)}n.$

n \sum_{i = 1}^{k} \frac{\log^{(i)} n + 2 \log i}{i (\log i)^{3} \log^{(i)} n} \leq n \sum_{i = 1}^{\infty} \frac{3}{i (\log i)^{2}} = c n

$n\sum_{i=1}^k\frac{\log^{(i)}n+2\log i}{i(\log i)^3\log^{(i)}n}\le n\sum_{i=1}^\infty\frac{3}{i(\log i)^2}=cn$

c

$c$

Emil Jeřábek
fuente

$O(n)$ $n\cdot(1+o(1))$

$n$ $\{1,2,\ldots,n\}$ $i'th$ $i$

RB
fuente