Estructura de datos basada en comparación para encontrar elementos

¿Existe una estructura de datos que toma una matriz desordenada de elementos, realiza un preprocesamiento en y responde consultas: ¿hay algún elemento en la lista, cada consulta en el peor momento ? $n$ $O(n)$ $x$ $O(\log n)$

Realmente creo que no hay, así que una prueba de que no hay ninguno también es bienvenida

ds.data-structures sorting Chi-Lan
fuente

(1) No sé por qué puede decir "Por supuesto que considero el tiempo esperado", porque no dice "esperado" en su pregunta. Por favor, intente afirmar su pregunta con más precisión antes de decir (2) Por favor, defina “por supuesto.” “No hashable.”

Tsuyoshi Ito

(1) Ya veo. Gracias por la explicación. Si alguien pregunta "¿Te importa el tiempo de ejecución?", Entonces la respuesta sería "por supuesto" :) (2) Creo que "la única acción permitida es comparar dos valores en la lista" es mucho más precisa que simplemente decir "no hashable". ¿Puede editar la pregunta para que las personas no tengan que leer los comentarios para entender lo que significa "no hashable"?

Tsuyoshi Ito

Por cierto, si no puedes probarlo, ¿por qué sabes que es imposible? Si se trata de un ejercicio en un libro de texto o una clase, está preguntando en un sitio web incorrecto.

Tsuyoshi Ito

¿Es esta su pregunta? ¿Existe una estructura de datos que tome una matriz desordenada de n elementos, realice el preprocesamiento en O (n) y responda consultas: ¿hay algún elemento x en la lista, cada consulta en el peor momento O (log n)?

sdcvvc

@Filip: ¿Es fácil de ver? Si es cierto, entonces estoy de acuerdo en que resuelve la pregunta.

Tsuyoshi Ito

Respuestas:

Aquí hay una prueba de que es imposible. Suponga que puede construir una estructura de datos de este tipo. Constrúyelo. Luego elija $n/\log n$ elementos al azar de la lista, agregue $\epsilon$ a cada uno de ellos, donde $\epsilon$ es menor que la diferencia entre dos elementos en la lista, y realice las consultas para verificar si alguno de los elementos resultantes está en el lista. Ha realizado consultas $O(n)$ hasta ahora.

Me gustaría afirmar que las comparaciones que ha realizado son suficientes para determinar si un elemento en la lista original es menor o mayor que cualquier elemento nuevo . Supongamos que no pudieras decirlo. Entonces, debido a que este es un modelo basado en la comparación, no sabría si era igual a o no, una contradicción de la suposición de que su estructura de datos funciona. $a$ $b$ $a$ $b$

Ahora, dado que los elementos que eligió fueron aleatorios, sus comparaciones con alta probabilidad han dado suficiente información para dividir la lista original en listas cada una de tamaño . Al ordenar cada una de estas listas, obtienes un algoritmo de ordenación aleatorio de tiempo basado únicamente en comparaciones, una contradicción. $n/\log n$ $n/\log n$ $O(\log n)$ $O(n \log \log n)$

Peter Shor
fuente

Algunos consejos para ayudar a comprender la prueba (suponiendo que yo mismo lo entiendo correctamente, por supuesto): los elementos

deben ser completados por los elementos después de que se les haya agregado

; las garantías modelo de comparación que saben cuáles de los casos

bodegas; las listas

están en 'orden ascendente': cada elemento en cualquier lista superior es más alto que cada elemento en cualquier lista inferior; después de las consultas originales, tiene suficiente información para hacer las listas alrededor de los elementos que eligió al azar,

b

$b$

ϵ

$\epsilon$

a \leq b

$a \leq b$

a \geq b

$a \geq b$

n / \log n

$n / \log n$

Alex ten Brink

(continuación) tenga en cuenta que ni siquiera tiene que poder construir explícitamente la lista en el tiempo proporcionado para que la prueba se mantenga.

Alex ten Brink

No entiendo esta prueba en silencio. La contradicción final es "algoritmo basado únicamente en comparaciones", pero en los primeros pasos de nuestro algoritmo agregamos

a cada elemento (además, "donde

es más pequeño que la diferencia entre dos elementos en la lista"). ¿Por qué seguimos justificando que nuestro algoritmo todavía solo se basa en la comparación si asumimos que nuestros artículos tienen un orden total no discreto?

ϵ

$\epsilon$

ϵ

$\epsilon$

Artem Kaznatcheev

@Artem: Su entrada original se compone de elementos

. Luego construyes un nuevo conjunto

; usted representa una

original como

y una

modificada como

. Ahora usa el algoritmo de caja negra; el algoritmo compara elementos de

x \in X

$x \in X$

X^{'} = X \times {0, 1}

$X' = X \times \{0,1\}$

x \in X

$x \in X$

(x, 0) \in X^{'}

$(x,0) \in X'$

x + ϵ

$x + \epsilon$

(x, 1) \in X^{'}

$(x,1) \in X'$

X^{'}

$X'$ el uno al otro; Para responder a estas consultas, solo necesita comparar un número constante de elementos de

entre sí. Por lo tanto, todo debería ser factible en el modelo de comparación, con una sobrecarga constante.

X

$X$

Jukka Suomela

@Aryabhata: lo hace. ¿Qué es el algoritmo

O (\log^{2} n)

$O(\log^2 n)$

Peter Shor el

Creo que aquí hay una prueba diferente, que demuestra la imposibilidad de una estructura de tiempo de consulta , con preprocesamiento . $\mathcal{O}(\log ^k n)$ $\mathcal{O}(n)$

Suponga que en el preprocesamiento realiza comparaciones , lo que lleva a un orden parcial. $\mathcal{O}(n)$

Ahora considere el tamaño del antichain más grande en eso. Dado que estos elementos no son comparables, para que tengamos un algoritmo de consulta , debemos tener que . $A$ $\mathcal{O}(\log ^k n)$ $A = \mathcal{O}(\log ^k n)$

Ahora, según el teorema de Dilworth, hay una partición de tamaño , en cadenas. $A$

Ahora podemos complementar el algoritmo para determinar las cadenas en la partición. Podemos determinar si dos elementos son comparables creando un gráfico dirigido de comparaciones y haciendo un análisis de accesibilidad. Esto se puede hacer sin comparaciones adicionales. Ahora solo fuerza bruta cada posible partición de tamaño para determinar si es una partición de cadenas. $A$

Una vez que tenemos las cadenas, podemos fusionarlas para obtener un algoritmo de comparación para ordenar la lista completa. $\mathcal{O}(n \log \log n)$

Aryabhata
fuente

Esta es una buena idea. Y si pudiera mostrar que la partición de la cadena debe ser conocida por el algoritmo, entonces podría usar mergesort para mostrar que solo se necesitarían comparaciones adicionales de O (n log log n) para ordenar toda la entrada, en lugar de usar Jensen. Pero hay un problema: ¿por qué el algoritmo de preprocesamiento debe construir una partición en cadena? Debe existir una partición en cadena, sí, pero eso es muy diferente de lo que el algoritmo conoce.

David Eppstein el

Ok, ahora creo en esta prueba. Y muestra con mayor firmeza que para lograr el tiempo de consulta de Polylog, debe utilizar una serie de comparaciones que se encuentran dentro de un aditivo

de clasificación. Agradable. Por cierto, la partición de la cadena se puede encontrar en tiempo polinómico a partir del conjunto de comparaciones ya realizadas, en lugar de necesitar una búsqueda de fuerza bruta, pero eso no hace ninguna diferencia para su argumento.

O (n \log \log n)

$O(n\log\log n)$

David Eppstein el

Las pruebas realmente muestran que debe tener un preprocesamiento

para cada consulta. Por supuesto, ambos son apretados. Esto muestra que la búsqueda binaria y la búsqueda lineal son los únicos algoritmos de búsqueda "interesantes" (al menos en el mundo clásico).

Ω (n \log n)

$\Omega(n\log n)$

Ω (n)

$\Omega(n)$

Yuval Filmus

@Yuval: tal vez deberías escribir esta observación como una respuesta real, porque me parece que tienes que hacer una cantidad moderada de trabajo para obtener el resultado anterior de las pruebas en las respuestas.

Peter Shor

@Yuval: pensamiento acerca de las pruebas, solamente veo que usted debe tener ya sea

el procesamiento previo o

tiempo de consulta para todos

. Es posible tener tiempo de preprocesamiento

y tiempo de consulta

. Se puede dividir la lista en

listas de tamaño

cada una en el tiempo

Ω (n \log n)

$\Omega(n \log n)$

Ω (n^{1 - ϵ})

$\Omega(n^{1-\epsilon})$

ϵ

$\epsilon$

o (n \log n)

$o(n \log n)$

O (n / \log n)

$O(n / \log n)$

\log n

$\log n$

n / \log n

$n/\log n$

usando la búsqueda repetida de mediana.

θ (n \log \log n)

$\theta(n \log\log n)$

Peter Shor

Como señala la respuesta de Peter Shor, para descartar la membresía en un modelo basado en la comparación, necesitamos saber cómo se compara el elemento con cada miembro. Por lo tanto, utilizando consultas aleatorias (el número de miembros más pequeños que el no miembro consultado es aleatorio), obtenemos información relación con tener valores no ordenados. Por lo tanto, para alguna constante , usando $k<n$ $Θ(n \log k)$ $n$ $c>0$ preprocesamiento, no podemos tener $c \, n \log k$ costo de consulta. Esto es óptimo hasta un factor constante, ya que podemos clasificar los datos en cubos aproximadamente iguales (cada cubo sin clasificar) en tiempo, que permite elcosto de consulta . $≤c \, n \log k/k$ $k' = k / \log k ≤ n/\log n$ $O(n \log k') = O(n \log k)$ $O(n/k')$

En particular, usando el preprocesamiento , no podemos tener un costo de consulta . Además, el preprocesamiento de corresponde a en por cada y, por lo tanto, el costo de consulta de . $O(n)$ $o(n)$ $o(n \log n)$ $k$ $O(n^ε)$ $ε>0$ $Ω(n^{1−ε})$

Dmytro Taranovsky
fuente