Considere el siguiente problema:
Entrada : enumera de enteros
Objetivo : determinar si existe un número entero que está en ambas listas.
Supongamos que ambas listas son de tamaño n . ¿Existe un algoritmo determinista de tiempo lineal para este problema? En otras palabras, ¿puedes resolver este problema en O ( n ) tiempo de manera determinista, sin usar aleatoriedad?
Desafortunadamente, no puede asumir que los elementos de la lista son todos pequeños.
Puedo ver cómo resolverlo en tiempo esperado usando un algoritmo aleatorio: elija aleatoriamente una función hash 2-universal h , almacene los elementos de X en una tabla hash (usando h como la función hash), y luego busque cada elemento de Y para ver si está en la tabla hash. El tiempo de ejecución esperado será O ( n ) . Sin embargo, no puedo ver cómo encontrar un algoritmo determinista con O ( n ) tiempo de ejecución. Si intenta desrandomizar esto y corregir una única función hash específica, existirá una entrada en el peor de los casos que hará que este procedimiento se ejecute en tiempo. El mejor algoritmo determinista que puedo encontrar implica ordenar los valores, pero eso no será en tiempo lineal. ¿Podemos lograr un tiempo de ejecución lineal?
Además, puedo ver cómo resolverlo en tiempo lineal si supones que todos los elementos de la lista son enteros en el rango (básicamente, hacer un recuento), pero estoy interesado en lo que sucede en general caso cuando no podemos asumir eso.
Si la respuesta depende del modelo de computación, el modelo RAM salta a la mente, pero me interesarían los resultados para cualquier modelo razonable de computación. Soy consciente de los límites inferiores de para los algoritmos del árbol de decisión para la unicidad del elemento , pero esto no es definitivo, ya que a veces podemos encontrar algoritmos de tiempo lineal incluso cuando hay un Ω ( n log n ) vinculado en El modelo del árbol de decisión.
Respuestas:
Puede resolver el problema en tiempo lineal si tiene suficiente memoria para tener un bit para cada valor posible en X e Y. Esto no impone ninguna restricción en el orden de X e Y.
fuente
Como está diciendo que las dos listas contienen números enteros, creo que podemos ejecutar una clasificación de radix en las dos listas y luego hacer una búsqueda lineal comparando las dos listas para elementos equivalentes.
fuente
fuente
fuente