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 el 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 singularidad 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 los límites superior como inferior de su complejidad temporal son del orden de la función linealitmica en el modelo de cálculo de árbol de decisión algebraico , [2] un modelo de cálculo en el que los elementos no se pueden utilizar para indexar la memoria de la computadora (como en la solución de la tabla hash), sino que solo se puede acceder a ellos calculando y comparando funciones algebraicas simples de sus valores. En otras palabras, un asintóticamente óptimoPara este modelo se conoce el algoritmo de complejidad lineal del tiempo. El modelo de árbol de cálculo algebraico básicamente significa que los algoritmos permitidos son solo los 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ápidamente, 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 suficientemente grande. [6] Ambainis [7] y Kutin [8] independientemente (ya través de diferentes pruebas) ampliaron su trabajo para obtener el límite inferior para todas las funciones.
Los elementos que ocurren más de n / k veces en un conjunto múltiple de tamaño n pueden encontrarse en el tiempo O ( n log k ). El problema de la distinción de elementos es un caso especial de k = n . Este algoritmo es óptimo bajo el modelo de cálculo de árbol de decisión . [9]