Algoritmo para encontrar la diferencia más pequeña en la matriz

Queremos un algoritmo que, dada una matriz de longitud $n$ de enteros, encuentre la diferencia mínima entre dos enteros en la matriz.

Uno de estos algoritmos es ordenar la matriz y verificar pares de números adyacentes. Esto lleva tiempo $O(n\log n)$ .

¿Hay una forma más rápida, por ejemplo, un $O(n)$ ¿algoritmo?

algorithms arrays comido
fuente

O (n)

$O(n)$ no es más rápido que

O (n \log n)

$O(n\log n)$

David Merinos

Respuestas:

Esto depende de su modelo de cálculo. Si solo permite la aritmética y las comparaciones (el modelo de árbol de decisión algebraico), entonces hay un $\Omega(n\log n)$ límite inferior para la distinción de elementos , el problema de decidir si todos los elementos son distintos. Su problema es, por supuesto, aún más difícil, por lo que se aplica el mismo límite inferior.

(Hay algunas letras pequeñas: el límite inferior solo se mantiene si el grado de los polinomios que se comparan está limitado. Si todo lo que está haciendo es comparar varias diferencias $x_i - x_j$ , entonces estás listo para irte. El modelo de árbol de decisión algebraico también le permite comparar polinomios más generales en las entradas, siempre que tengan un grado acotado).

Hay otros modelos que podrían funcionar mejor, por ejemplo, en algunos modelos puede ordenar enteros en $o(n\log n)$ . Pero me imagino que no quieres permitir el tipo de truco utilizado en tales algoritmos.

Yuval Filmus
fuente

Gracias. ¿Qué quieres decir con "comparar varias diferencias

x_{i} - x_{j}

$x_i-x_j$ "? Puesto que hay

Θ (n^{2})

$\Theta(n^2)$ tales pares, no tomaría eso tiempo

Ω (n^{2})

$\Omega(n^2)$ ?

Expulsado el

No necesariamente. Los algoritmos basados en comparación solo pueden comparar pares de elementos. Aquí te estoy permitiendo hacer consultas más complicadas como

x_{1} - x_{2} > x_{3} - x_{4}

$x_1 - x_2 > x_3 - x_4$ , o incluso

x_{1} + 5 x_{8} - 17 x_{3} < - 5

$x_1 + 5x_8 - 17x_3 < -5$ . Sabemos que hay una solución que usa

O (n \log n)

$O(n\log n)$ comparaciones del tipo

x_{i} > x_{j}

$x_i > x_j$ y

O (n)

$O(n)$ comparaciones del tipo

x_{i} - x_{j} > x_{k} - x_{ℓ}

$x_i - x_j > x_k - x_\ell$ . La pregunta es, ¿puede hacerlo mejor?

Yuval Filmus el

No estoy seguro de entender el significado práctico de este límite para la distinción de elementos. ¿No tendría una O (n) esperada con una tabla hash?

jkff

No se puede implementar una tabla hash utilizando este modelo de cálculo. En general, los límites inferiores son difíciles de probar. El modelo de árbol de decisión algebraico es uno en el que los límites inferiores no triviales son demostrables. No veo como probar un

ω (n)

$\omega(n)$ límite inferior en cualquier otro modelo; de hecho, tales límites inferiores generalmente se conocen solo para funciones aleatorias. Tienes razón en que puede haber un truco

o (n \log n)

$o(n\log n)$ algoritmo que va más allá de este modelo, pero no se me ocurre ninguno.

Yuval Filmus

-1

Si los enteros en la matriz tienen un número limitado de dígitos, puede ordenar una matriz con el algoritmo de clasificación de radix , eso es O (kN) y luego verificar los pares de números adyacentes (O (N))? La complejidad resultante será O ((k + 1) N), lineal.

Pavel Davydov
fuente

Tenga en cuenta las condiciones bajo las cuales el tiempo de ejecución de la clasificación de radix es realmente bueno.

Raphael

@Raphael Bueno, la pregunta original era si existe el algoritmo lineal, así que lo pensé. ¿Quiere decir que k será mayor que log (N) para N pequeño?

Pavel Davydov el

k

$k$ y

N

$N$ son parámetros independientes, por lo que la ordenación por radix no es un algoritmo de tiempo lineal para todas las entradas y, por lo tanto, no contradice el

Ω (n \log n)

$\Omega(n \log n)$ vinculado a la clasificación (de comparación). (El artículo de Wikipedia también explica esto.)

Raphael

@Raphael Sí, pero para una matriz de enteros que son menos de 64 bits (ese es un caso bastante común) será lineal. Editaré mi respuesta. Gracias por tus comentarios.

Pavel Davydov