Problema de distinción de elementos
En la teoría de la complejidad computacional , el problema de distinción de elementos o el 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 puede resolverse 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 prueban 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.
Se sabe que, para listas de números, la complejidad temporal del problema es Θ ( n log n ), es decir, tanto el límite superior como el inferior de su complejidad temporal son del orden de la función lineal rítmica en el modelo de cálculo de árbol de decisión algebraico , [2] un modelo de computación en el que los elementos no se pueden usar para indexar la memoria de la computadora (como en la solución de la tabla hash), pero solo se puede acceder a ellos computando y comparando funciones algebraicas simples de sus valores. En otras palabras, un asintóticamente óptimoPara este modelo se conoce un algoritmo de complejidad temporal lineal rítmica. El modelo de árbol de cálculo algebraico básicamente significa que los algoritmos permitidos son solo aquellos que pueden realizar operaciones polinómicas de grado acotado en los datos de entrada y comparaciones de los resultados de estos cálculos.
También se sabe que los algoritmos cuánticos pueden resolver este problema más rápido, en consultas. El algoritmo óptimo es de Andris Ambainis . [5] Yaoyun Shi demostró por primera vez un límite inferior ajustado cuando el tamaño del rango es lo suficientemente grande. [6] Ambainis [7] y Kutin [8] de forma independiente (ya través de diferentes demostraciones) ampliaron su trabajo para obtener el límite inferior de todas las funciones.
Los elementos que ocurren más de n / k veces en un conjunto múltiple de tamaño n se pueden encontrar en el tiempo O ( n log k ). El problema de distinción de elementos es un caso especial de k = n . Este algoritmo es óptimo bajo el modelo de cálculo del árbol de decisión . [9]