problema de distinción de elementos

En la teoría de la complejidad computacional , el problema de la distinción de elementos o el problema de la unicidad de elementos consiste en determinar si todos los elementos de una lista son distintos.

Es un problema ampliamente estudiado en diversos modelos de computación. Puede resolverse ordenando la lista y comprobando si existen elementos consecutivos iguales; también puede resolverse en tiempo lineal esperado mediante un algoritmo aleatorio que inserta cada elemento en una tabla hash y compara únicamente aquellos elementos ubicados en la misma celda de la tabla hash. ^{[ 1 ]}

Se demuestran varios límites inferiores en la complejidad computacional reduciendo el problema de distinción de elementos al problema en cuestión, es decir, demostrando que la solución del problema de unicidad de elementos se puede encontrar rápidamente después de resolver el problema en cuestión.

El número de comparaciones necesarias para resolver el problema del tamaño${\displaystyle n}$, en un modelo de computación basado en comparaciones, como un árbol de decisión o un árbol de decisión algebraico , es${\displaystyle \Theta (n\log n)}$. Aquí,${\displaystyle \Theta }$invoca la notación big theta , lo que significa que el problema se puede resolver en una cantidad de comparaciones proporcional a${\displaystyle n\log n}$(una función linealítmica ) y que todas las soluciones requieren esta cantidad de comparaciones. ^{[ 2 ]} En estos modelos de computación, los números de entrada pueden no usarse para indexar la memoria de la computadora (como en la solución de tabla hash), sino que solo se puede acceder a ellos calculando y comparando funciones algebraicas simples de sus valores. Para estos modelos, un algoritmo basado en la ordenación por comparación resuelve el problema dentro de un factor constante del mejor número posible de comparaciones. El mismo límite inferior se aplica también al número esperado de comparaciones en el modelo de árbol de decisión algebraico aleatorio . ^{[ 3 ] [ 4 ]}

Si los elementos del problema son números reales , la cota inferior del árbol de decisión se extiende al modelo de máquina de acceso aleatorio real con un conjunto de instrucciones que incluye suma, resta y multiplicación de números reales, así como comparación y división o resto ("floor"). ^{[ 5 ]} De ello se deduce que la complejidad del problema en este modelo también es${\displaystyle \Theta (n\log n)}$Este modelo RAM abarca más algoritmos que el modelo de árbol de decisión algebraico, ya que incluye algoritmos que utilizan la indexación de tablas. Sin embargo, en este modelo se contabilizan todos los pasos del programa, no solo las decisiones.

Una máquina de Turing determinista de una sola cinta puede resolver el problema, para n elementos de m ≥ log n bits cada uno, en un tiempo O ( n ² m ( m +2–log n )) , mientras que en una máquina no determinista la complejidad temporal es O ( nm ( n + log m )) . ^{[ 6 ]}

Los algoritmos cuánticos pueden resolver este problema más rápido, en${\textstyle \Theta (n^{2/3})}$consultas. El algoritmo óptimo es de Andris Ambainis . ^{[ 7 ]} Yaoyun Shi demostró por primera vez una cota inferior ajustada cuando el tamaño del rango es suficientemente grande. ^{[ 8 ]} Ambainis ^{[ 9 ]} y Kutin ^{[ 10 ]} de forma independiente (y mediante diferentes demostraciones) extendieron su trabajo para obtener la cota inferior para todas las funciones.

Elementos que ocurren más de${\displaystyle n/k}$veces en un multiconjunto de tamaño${\displaystyle n}$puede encontrarse mediante un algoritmo basado en comparaciones, el algoritmo de los grandes éxitos de Misra-Gries , en el tiempo${\displaystyle O(n\log k)}$. El problema de la distinción de elementos es un caso especial de este problema donde${\displaystyle k=n}$. Este tiempo es óptimo bajo el modelo de cálculo de árbol de decisión . ^{[ 11 ]}

• Problema de colisión