Dada una matriz de enteros sin clasificar, y sin hacer ninguna suposición sobre los números en la matriz:
¿Es posible encontrar dos números cuya la diferencia es mínima en O (n) tiempo?¿Es posible encontrar dos números cuya diferencia es mínima en O (n) Tiempo de
Editar: diferencia entre dos números a, b se define como abs(a-b)
Encuentra el elemento más pequeño y grande de la lista. La diferencia más pequeña-más grande será mínima.
Si está buscando una diferencia no negativa, esto es, por supuesto, al menos tan difícil como comprobar si la matriz tiene dos elementos iguales. Esto se llama element uniqueness problem y sin ninguna suposición adicional (como limitar el tamaño de los enteros, permitiendo otras operaciones que la comparación) requiere> = n log n time. Es el caso unidimensional de encontrar el closest pair of points.
Creo que para un conjunto [5, 6, 1, 10] están buscando 1, no -9. –
@Kathy: Entonces deberían haber escrito "Encontrar dos * enteros * enteros cuyo * módulo * de diferencia sea mínimo". Especificador de advertencia :) –
+1 para pensar fuera de las suposiciones habituales de * diferencia *. –
No, no sin hacer suposiciones acerca de los números/pedido.
Sin embargo, sería posible obtener una lista ordenada.
No creo que se pueda en O (n). Lo mejor que se me ocurre es ordenarlos (que es O (n * log n)) y encontrar la diferencia mínima de pares adyacentes en la lista ordenada (que agrega otra O (n)).
Estoy pensando lo mismo, pero @Michael Todd dice que puedes hacerlo int O (n), así que estoy esperando ansiosamente para ver lo que publica –
@non sequitor: Espero que nos responda pronto. Estoy feliz de que se demuestre que estoy equivocado. :) –
Creo que estás cerca - un radixsort te da O (n) tiempo de ordenamiento, luego O (n) para la iteración del par adyacente. – fbrereto
Lo mejor que puedo pensar es en counting sort la matriz (posiblemente combinando valores iguales) y luego hacer las comparaciones ordenadas - bin es O (n + M) (M es el número de valores distintos). Sin embargo, esto tiene un gran requerimiento de memoria. Alguna forma de ordenación de balde o de cubo sería intermedia en el tiempo y más eficiente en el espacio.
Probablemente tengas que usar el tipo de raíz, ¿no? No se te da el posible rango de números, por lo que el conteo de los números estaría inmediatamente fuera de la ventana. –
Encontrar el rango es una operación O (n) (mínimo, máximo). –
Sí, pero el rango puede ser arbitrariamente grande en este caso.Ver el comentario de Bill the Lizard sobre su respuesta. – PeterAllenWebb
Ordene la lista con radixsort (que es O (n) para enteros), luego repita y realice un seguimiento de la distancia más pequeña hasta el momento.
(supongo que el número entero es un tipo de bits fija. Si son capaces de mantener arbitrariamente grandes números enteros matemáticos, Ordenamiento Radix será O (n log n) también.)
No creo que tengas garantizado que k sea constante aquí. ¿Qué pasa si k = n? –
El ordenamiento de radix es solo O (n) porque crea límites en el algoritmo. Si está ordenando valores int normales que se garantiza que son únicos, en realidad es O (1). Si está ordenando números arbitrariamente grandes, ya no es O (n). –
Tiene razón; entero puede referirse a un tipo de datos de longitud variable. He editado mi respuesta para establecer esa suposición. – meriton
Se seems a ser posible ordenar sin límites conjunto de enteros en O (n * sqrt (log (log (n))) tiempo. Después de ordenar es por supuesto trivial encontrar la diferencia mínima en tiempo lineal.
Pero no se me ocurre ningún algoritmo para hazlo más rápido que esto.
Creo que la respuesta es no y la prueba es similar a la prueba de que no puedes ordenar más rápido que n lg n: tienes para comparar todos los elementos, es decir, crear un árbol de comparación, lo que implica el algoritmo omega (n lg n).
EDIT. De acuerdo, si realmente quieres discutir, entonces la pregunta no dice si debería ser una máquina de Turing o no. Con las computadoras cuánticas, puede hacerlo en tiempo lineal :)
¿Por qué tiene que comparar todos los elementos? Obviamente necesitas mirarlos, pero ¿por qué * comparar *? – meriton
OK, llamémoslo "mirar números", de todos modos, habrá un árbol de comparación. –
Aún asumes que cada buen algoritmo para este problema comparará y construirá árboles de comparación. Como no justificas esta suposición, tu prueba es incompleta. – meriton
Creo que es posible. El secreto es que en realidad no tienes que ordenar la lista, solo necesitas crear un recuento de los números que existen. Esto puede contar como "hacer una suposición" desde una perspectiva algorítmica, pero no desde una perspectiva práctica. Sabemos que las entradas están limitadas por un mínimo y un máximo.
Por lo tanto, crear una matriz de elementos 2 bits, 1 par para cada int de INT_MIN a INT_MAX inclusive, establecer todos ellos a 00.
iterar a través de toda la lista de números. Para cada número en la lista, si los 2 bits correspondientes son 00, configúrelos en 01. Si son 01, configúrelos en 10. De lo contrario, ignore. Esto es obviamente O (n).
A continuación, si alguno de los 2 bits está configurado en 10, esa es su respuesta. La distancia mínima es 0 porque la lista contiene un número repetido. De lo contrario, explore la lista y encuentre la distancia mínima. Mucha gente ya ha señalado que hay algoritmos O (n) simples para esto.
Entonces O (n) + O (n) = O (n).
Editar: responder a los comentarios.
Puntos interesantes. Creo que podría lograr los mismos resultados sin hacer ninguna suposición encontrando el mínimo/máximo de la lista primero y usando una matriz dispersa que va desde el mínimo al máximo para contener los datos. Se ocupa de la suposición INT_MIN/MAX, la complejidad del espacio y la complejidad del tiempo de O (m) al escanear el conjunto.
¿Quién dice que se está implementando en un sistema con números de tamaño finito? –
Si su algoritmo se basa en que las entradas están limitadas por un mínimo y un máximo, en realidad es O (1). Dado un máximo en n, la operación llevará un tiempo limitado. –
La longitud de la matriz no está en O (n), pero supone que se inicializó con 00 elementos. Además, ¿cómo exploras * la lista * para encontrar la distancia más pequeña? – meriton
¿podría engañar su camino y buscar los mismos dos enteros, ya que su diferencia sería la mínima? –
@aforloney - Creo que el requisito "sin hacer ninguna suposición sobre los números en la matriz" lo descartaría. –
@aflorloney: depende de su definición de mínimo. (10 - 10)> (2 - 3). – Juliet