Clasificación X + Y

Problema sin resolver en informática

¿Hay un?${\displaystyle X+Y}$algoritmo de ordenación más rápido que${\displaystyle O(n^{2}\log n)}$¿

Más problemas sin resolver en informática

En informática , la ordenación X + Y consiste en ordenar pares de números según sus sumas. Entre las aplicaciones de este problema se incluyen la minimización de tarifas de transporte público , el diseño VLSI y la multiplicación de polinomios dispersos . Al igual que con la ordenación por comparación y la ordenación de enteros en general, los algoritmos para este problema pueden basarse únicamente en comparaciones de estas sumas o en otras operaciones que solo funcionan cuando las entradas son enteros pequeños.

Se desconoce si este problema tiene una solución basada en comparaciones cuyo tiempo de ejecución sea asintóticamente más rápido que ordenar una lista no estructurada con la misma cantidad de elementos. Por lo tanto, la investigación sobre el problema se ha centrado en dos enfoques para dilucidar si tal mejora es posible: el desarrollo de algoritmos que mejoran la ordenación no estructurada en cuanto al número de comparaciones, en lugar de en su tiempo de ejecución total, y los límites inferiores para el número de comparaciones basados ​​en el conteo de celdas en subdivisiones de espacios de alta dimensión. Ambos enfoques están históricamente relacionados, ya que los primeros algoritmos que utilizaban pocas comparaciones se basaban en la debilidad de los límites inferiores del conteo de celdas.

La entrada a la${\displaystyle X+Y}$El problema de ordenación consiste en dos colecciones finitas de números.${\displaystyle X}$y${\displaystyle Y}$, de la misma longitud. La salida del problema es la colección de todos los pares de un número de${\displaystyle X}$y un número de${\displaystyle Y}$, ordenados según la suma de cada par. ^{[ 1 ]} Como pequeño ejemplo, para las entradas${\displaystyle X=\{1,2,9\}}$y${\displaystyle Y=\{0,4,9\}}$, la salida debe ser la lista de pares$${\displaystyle (1,0),\,(2,0),\,(1,4),\,(2,4),\,(9,0),\,(1,9),\,(2,9),\,(9,4),\,(9,9)}$$de un elemento de${\displaystyle X}$y un elemento de${\displaystyle Y}$, ordenados según la suma de sus pares$${\displaystyle 1,2,5,6,9,10,11,13,18.}$$Una forma de resolver el problema sería construir los pares a ordenar (el producto cartesiano de las dos colecciones) y usar estos pares como entrada para un algoritmo de ordenación por comparación estándar como merge sort o heapsort . Cuando las entradas tienen longitud${\displaystyle n}$ellos forman${\displaystyle n^{2}}$pares, y el tiempo para ordenar los pares de esta manera es${\displaystyle O(n^{2}\log n)}$En términos de su notación O grande , este método es el algoritmo más rápido conocido para${\displaystyle X+Y}$ordenación. Si existe un algoritmo más rápido es un problema abierto , ^{[ 1 ] [ 2 ]} planteado por Elwyn Berlekamp antes de 1975. ^{[ 1 ] [ 3 ]}

Una variante del problema ordena el conjunto suma , el conjunto de sumas de pares, con las sumas duplicadas condensadas en un solo valor. Para esta variante, el tamaño del conjunto suma puede ser significativamente menor que${\displaystyle n^{2}}$y se han investigado algoritmos sensibles a la salida para su construcción. ^{[ 4 ]}

Steven Skiena relata una aplicación práctica en la minimización de tarifas de transporte , un ejemplo del problema del camino más corto : encontrar el billete de avión de dos saltos más barato entre dos ciudades dadas, a partir de una entrada que describe tanto el coste de cada salto como qué pares de saltos se pueden combinar en un solo billete. La solución de Skiena consiste en ordenar pares de saltos por su coste total como un ejemplo del problema del camino más corto.${\displaystyle X+Y}$problema de ordenación, y luego probar los pares resultantes en este orden ordenado hasta encontrar uno que esté permitido. Para generar los pares ordenados en este orden, Skiena utiliza una cola de prioridad de pares, que inicialmente contiene solo un par, el que consta de los dos saltos más baratos. Luego, cuando un par${\displaystyle (x,y)}$se elimina de la cola y se determina que no está permitido, se agregan dos pares más, y uno de estos dos pares se combina${\displaystyle x}$con el siguiente salto después${\displaystyle y}$en una lista ordenada de los saltos hasta el destino, y el otro par combinando${\displaystyle y}$con el siguiente salto después${\displaystyle x}$en una lista ordenada de saltos desde el inicio. De esta manera, cada par sucesivo se puede encontrar en tiempo logarítmico, y solo es necesario ordenar los pares hasta el primero permitido. ^{[ 2 ]}

${\displaystyle X+Y}$La ordenación es la subrutina más costosa en un algoritmo para un problema en el diseño VLSI , en el que se deben colocar dos subunidades de un circuito VLSI una al lado de la otra a lo largo de un canal de comunicaciones para minimizar el ancho del canal necesario para enrutar pares de cables de una subunidad a la otra. A medida que una subunidad se desplaza continuamente con respecto a la otra, el ancho del canal solo cambia en posiciones discretas donde los extremos de dos cables se alinean entre sí, y encontrar el orden ordenado de estas posiciones para calcular la secuencia de cambios en el ancho se puede realizar mediante${\displaystyle X+Y}$ordenación. Si se pudiera acelerar este problema de ordenación, también se aceleraría esta tarea de diseño VLSI. ^{[ 5 ]}

Otra aplicación implica la multiplicación de polinomios para polinomios de una sola variable que pueden tener muchos menos términos que sus grados . El producto de dos polinomios se puede expresar como una suma de productos de pares de términos, uno de cada polinomio, y colocar estos productos término por término en orden de grado equivale a ordenarlos por la suma de los grados. Por ejemplo, el caso de${\displaystyle X+Y}$clasificar con${\displaystyle n=3}$El ejemplo anterior corresponde a la multiplicación de dos polinomios de tres términos para producir un polinomio de nueve términos: $${\displaystyle {\begin{aligned}(&x+x^{2}+x^{9})(1+x^{4}+x^{9})\\&=x+x^{2}+x^{5}+x^{6}+x^{9}+x^{10}+x^{11}+x^{13}+x^{18}.\\\end{aligned}}}$$ Los grados son siempre enteros, por lo que los algoritmos basados ​​en enteros para${\displaystyle X+Y}$Se puede aplicar la ordenación. ^{[ 6 ]} Sin embargo, para polinomios cuyo número de términos es comparable a su grado, los algoritmos de multiplicación de polinomios basados ​​en FFT pueden ser significativamente más eficientes que la multiplicación término por término. ^{[ 7 ]}

Un límite inferior bien conocido para la ordenación no estructurada, en el modelo de árbol de decisión , se basa en el número factorial de órdenes ordenados que puede tener una lista no estructurada. Debido a que cada comparación puede, en el mejor de los casos, reducir el número de posibles ordenaciones en un factor de dos, la ordenación requiere un número de comparaciones al menos igual al logaritmo binario del factorial, que es${\displaystyle n\log _{2}nO(n)}$. ^{[ 8 ]} Primeros trabajos sobre${\displaystyle X+Y}$La clasificación siguió un enfoque similar preguntando cuántos ordenamientos diferentes son posibles para este problema y demostrando que este número es como máximo${\displaystyle O(n^{8n})}$Sin embargo, debido a que su logaritmo binario es como máximo${\displaystyle 8n\log _{2}n+O(1)}$, mucho más pequeño que los límites de tiempo conocidos para${\displaystyle X+Y}$ordenación, este método solo puede conducir a límites inferiores débiles en el número de comparaciones. ^{[ 3 ] [ 9 ]}

La prueba de este límite se relaciona${\displaystyle X+Y}$ordenación según la complejidad de una disposición de hiperplanos en geometría de alta dimensión. Las dos colecciones de entrada para la${\displaystyle X+Y}$el problema de clasificación comprende${\displaystyle 2n}$números, que alternativamente pueden interpretarse como las coordenadas cartesianas de un punto en el${\displaystyle 2n}$espacio dimensional${\displaystyle \mathbb {R} ^{2n}}$Este espacio se puede subdividir en celdas, de modo que dentro de una sola celda todos los puntos corresponden a entradas que producen el mismo orden ordenado. Para esta subdivisión, cada límite entre dos celdas se encuentra dentro de un hiperplano definido por una igualdad de pares.${\displaystyle x_{i}+y_{j}=x_{k}+y_{\ell }}$, dónde${\displaystyle (x_{i},y_{j})}$y${\displaystyle (x_{k},y_{\ell })}$son dos pares cuyo orden cambia de una celda adyacente a la otra. Estos hiperplanos son generados por dos pares disjuntos o tienen las formas simplificadas.${\displaystyle x_{i}=x_{k}}$o${\displaystyle y_{j}=y_{\ell }}$, por lo que el número de hiperplanos distintos que se pueden determinar de esta manera es $${\displaystyle k=2{\binom {n}{2}}^{2}+2{\binom {n}{2}}.}$$ El número de celdas que este número de hiperplanos puede dividir un espacio de dimensión${\displaystyle 2n}$en es $${\displaystyle {\binom {k}{2n}}+{\binom {k}{2n-1}}+\cdots +{\binom {k}{0}}=O(n^{8n}).}$$Por lo tanto, el conjunto${\displaystyle X+Y}$tiene${\displaystyle O(n^{8n})}$diferentes posibles ordenamientos ordenados. ^{[ 3 ] [ 9 ] [ 10 ]}

Un estilo de análisis similar ha tenido más éxito al descartar soluciones rápidas a ciertas generalizaciones de${\displaystyle X+Y}$clasificación, al demostrar que tienen demasiados ordenamientos para clasificar rápidamente. En particular, Harper et al. (1975) sugieren clasificar por separado${\displaystyle X}$y${\displaystyle Y}$y luego construir una matriz bidimensional de los valores de${\displaystyle X+Y}$que se ordena tanto por filas como por columnas antes de usar estos datos parcialmente ordenados para completar la ordenación.${\displaystyle X+Y}$[ ^{3 ]} Esta idea de utilizar una matriz ordenada por filas y columnas constituye la base del método utilizado por Skiena en la aplicación de transporte, ^{[ 2 ] y} puede reducir el número de comparaciones en un factor constante en relación con la ordenación por comparación ingenua. Sin embargo, para matrices cuyas filas y columnas están ordenadas de esta manera, el número de posibles ordenaciones de toda la matriz es mucho mayor que${\displaystyle O(n^{8n})}$, tan grande que cualquier algoritmo de ordenación por comparación que pueda funcionar para arbitrariamente${\displaystyle n\times n}$Las matrices que están ordenadas por filas y columnas aún requieren${\displaystyle \Omega (n^{2}\log n)}$comparaciones. Por lo tanto, si el${\displaystyle X+Y}$El problema de ordenación debe resolverse rápidamente; la solución debe utilizar información adicional sobre el conjunto.${\displaystyle X+Y}$más allá de este ordenamiento matricial. ^{[ 3 ]}

Para el problema clásico de ordenación por comparación, el tiempo para ordenar y el número de comparaciones necesarias para ordenar están dentro de factores constantes entre sí. Pero para${\displaystyle X+Y}$ordenando, el número de comparaciones es menor que el mejor límite de tiempo conocido: Michael Fredman demostró en 1976 que${\displaystyle X+Y}$La clasificación se puede realizar utilizando únicamente${\displaystyle O(n^{2})}$comparaciones. De manera más general, demostró que cualquier conjunto de${\displaystyle N}$elementos, cuyo ordenamiento ordenado ya ha sido restringido a una familia${\displaystyle \Gamma }$de pedidos, se pueden ordenar usando${\displaystyle \log _{2}|\Gamma |+O(N)}$comparaciones, mediante una forma de ordenación por inserción binaria . Para el${\displaystyle X+Y}$problema de ordenación,${\displaystyle N=n^{2}}$, y${\displaystyle |\Gamma |=O(n^{8n})}$, entonces${\displaystyle \log _{2}|\Gamma |=O(n\log n)}$y el límite de Fredman implica que solo${\displaystyle O(n^{2})}$Se necesitan comparaciones. Sin embargo, en el método de Fredman, el tiempo necesario para decidir qué comparaciones realizar puede ser significativamente mayor que el límite del número de comparaciones. ^{[ 9 ]}

El primer algoritmo explícito que logra ambos${\displaystyle O(n^{2})}$comparaciones y${\displaystyle O(n^{2}\log n)}$La complejidad total fue publicada dieciséis años después de Fredman por Lambert (1992) . El algoritmo realiza los siguientes pasos:

1. Ordena recursivamente los dos conjuntos.${\displaystyle X+X}$y${\displaystyle Y+Y}$.
2. Utilice la equivalencia${\displaystyle x_{i}-x_{j}\leq x_{k}-x_{\ell }\Leftrightarrow x_{i}+x_{\ell }\leq x_{j}+x_{k}}$para inferir los ordenamientos ordenados de${\displaystyle XX}$y${\displaystyle YY}$sin comparaciones adicionales.
3. Fusiona los dos conjuntos${\displaystyle XX}$y${\displaystyle YY}$en un único orden ordenado, utilizando una serie de comparaciones lineales en su tamaño total.
4. Utilice el orden combinado y la equivalencia${\displaystyle x_{i}+y_{j}\leq x_{k}+y_{\ell }\Leftrightarrow x_{i}-x_{k}\leq y_{\ell }-y_{j}}$para inferir el orden ordenado de${\displaystyle X+Y}$sin comparaciones adicionales.

La parte del algoritmo que ordena recursivamente${\displaystyle X+X}$(o equivalentemente${\displaystyle Y+Y}$) lo hace siguiendo los siguientes pasos:

1. Dividir${\displaystyle X}$en dos sublistas iguales${\displaystyle A}$y${\displaystyle B}$.
2. Ordenar recursivamente${\displaystyle A+A}$y${\displaystyle B+B}$
3. Inferir el orden en${\displaystyle A+B}$utilizando únicamente las comparaciones de un único paso de fusión como se indicó anteriormente.
4. Combinar los resultados ordenados${\displaystyle A+A}$,${\displaystyle B+B}$, y${\displaystyle A+B}$juntos.

El número de comparaciones${\displaystyle C(n)}$necesario para realizar este algoritmo recursivo en una entrada de${\displaystyle n}$Los elementos pueden analizarse utilizando la relación de recurrencia.$${\displaystyle C(n)\leq 2C(n/2)+O(n^{2}),}$$ donde el${\displaystyle 2C(n/2)}$El término de la recurrencia cuenta el número de comparaciones en las llamadas recursivas al algoritmo para ordenar.${\displaystyle A+A}$y${\displaystyle B+B}$y el${\displaystyle O(n^{2})}$El término cuenta el número de comparaciones utilizadas para fusionar los resultados. El teorema maestro para relaciones de recurrencia de esta forma muestra que${\displaystyle C(n)=O(n^{2}).}$La complejidad temporal total es más lenta,${\displaystyle O(n^{2}\log n)}$, debido a los pasos del algoritmo que utilizan comparaciones ya realizadas para inferir ordenaciones de otros conjuntos. Estos pasos se pueden realizar en tiempo${\displaystyle O(n^{2}\log n)}$mediante el uso de un algoritmo estándar de ordenación por comparación con sus pasos de comparación reemplazados por las inferencias indicadas. ^{[ 11 ]}

Si tan solo las comparaciones entre elementos de${\displaystyle X+Y}$Si se permiten, entonces también existe un límite inferior correspondiente.${\displaystyle \Omega (n^{2})}$en el número de comparaciones, ^{[ 9 ] [ 12 ]} pero con comparaciones más generales que involucran combinaciones lineales de números constantes de elementos, solo${\displaystyle O(n\log ^{2}n)}$Se necesitan comparaciones. ^{[ 13 ]}

Así como la ordenación de enteros puede ser más rápida que la ordenación por comparación para enteros suficientemente pequeños, lo mismo ocurre con${\displaystyle X+Y}$ordenación. En particular, con entradas enteras en el rango de${\displaystyle 0}$hasta cierto límite superior${\displaystyle M}$, el problema se puede resolver en${\displaystyle O(n+M\log M)}$operaciones mediante la transformada rápida de Fourier . ^{[ 1 ] [ 3 ]}

Otros problemas en geometría computacional tienen una complejidad equivalente o más difícil.${\displaystyle X+Y}$clasificación, incluyendo la construcción de sumas de Minkowski de polígonos escalonados, encontrar los puntos de cruce de una disposición de líneas en orden ordenado por su${\displaystyle x}$-coordenadas, listando pares de puntos ordenados según sus distancias, y probando si un polígono rectilíneo puede trasladarse para encajar dentro de otro. ^{[ 14 ]}

El problema de probar si dos de los pares en el${\displaystyle X+Y}$El problema de ordenación de sumas iguales se puede resolver ordenando los pares y luego comprobando la igualdad de pares consecutivos. A su vez, podría utilizarse para resolver el problema de 3SUM , lo que implica que es improbable que exista un algoritmo fuertemente subcuadrático. ^{[ 1 ]}