En la teoría de la complejidad computacional , el problema de distinción de elementos o problema de unicidad de elementos es el problema de determinar si todos los elementos de una lista son distintos.
Es un problema bien estudiado en muchos modelos diferentes de computación. El problema se puede resolver ordenando la lista y luego verificando si hay elementos iguales consecutivos; También se puede resolver en un tiempo esperado lineal mediante un algoritmo aleatorio que inserta cada elemento en una tabla hash y compara solo aquellos elementos que se colocan 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 puede encontrarse rápidamente después de resolver el problema en cuestión.
El número de comparaciones necesarias para resolver el problema de tamaño , en un modelo de cálculo basado en comparaciones, como un árbol de decisión o un árbol de decisión algebraico , es . Aquí, se invoca la notación theta grande , lo que significa que el problema se puede resolver en un número de comparaciones proporcionales a (una función linealítmica ) y que todas las soluciones requieren tantas comparaciones. [2] En estos modelos de cálculo, los números de entrada no se pueden usar 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 clasificació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 , el límite inferior del árbol de decisión se extiende al modelo de máquina real de acceso aleatorio 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 ( "piso"). [5] De ello se deduce que la complejidad del problema en este modelo también es . Este modelo de RAM cubre más algoritmos que el modelo de árbol de decisión algebraico, ya que abarca algoritmos que utilizan indexación en tablas. Sin embargo, en este modelo se cuentan todos los pasos del programa, no sólo las decisiones.
Una máquina de Turing determinista de cinta única puede resolver el problema, para n elementos de m ≥ log n bits cada uno, en el tiempo O ( n 2 m ( m +2–log n )) , mientras que en una máquina no determinista la complejidad temporal es O ( n m ( n + log m )) . [6]
Los algoritmos cuánticos pueden resolver este problema más rápido en las consultas. El algoritmo óptimo es el de Andris Ambainis . [7] Yaoyun Shi demostró por primera vez un límite inferior ajustado cuando el tamaño del rango es suficientemente grande. [8] Ambainis [9] y Kutin [10] de forma independiente (y mediante diferentes pruebas) ampliaron su trabajo para obtener el límite inferior para todas las funciones.
Los elementos que ocurren más de veces en un conjunto múltiple de tamaño se pueden encontrar en el tiempo mediante un algoritmo basado en comparación, el algoritmo de pesos pesados de Misra-Gries . El problema de distinción de elementos es un caso especial de este problema donde . Este tiempo es óptimo según el modelo de cálculo del árbol de decisión. [11]