¿Existe un algoritmo mejor que o (n) para el siguiente problema: dado que un hashset contiene enteros y un número, encuentra el número más cercano al número dado?

Realmente no. Pero más o menos.

Para vencer a [lo que podría decir con] O (n), no tendríamos que mirar ciertos elementos. Necesitaríamos alguna propiedad de pedido para descartar categóricamente grandes secciones del conjunto de datos, y no veo ninguna forma de hacerlo en un conjunto hash.

Sin embargo, en verdad, el problema simplemente no está bien definido. Eso posiblemente sugiere un malentendido de la gran O de su parte. [EDITAR: El problema ahora se ha aclarado para indicar que n es el número de elementos en el conjunto de hash.]

Hay dos soluciones razonables para este problema:

  1. Extraiga todos los valores del conjunto de hash y busque el más cercano a X.
  2. Redondea X a un número entero (si aún no lo está) y luego marca X-1, X + 1, X-2, X + 2, …

La primera solución es O (h), donde h es el número de elementos en su conjunto de hash.

La segunda solución es O (abs (Xc)), donde c es el valor más cercano a X.

Cuando dijiste O (n), ¿qué estabas definiendo como n? Estoy siendo un poco quisquilloso aquí, pero he encontrado que un montón de personas no entienden esto. N debe tener un significado . Muchas personas describirían la segunda solución como O (n), pero no es el mismo tiempo de ejecución que la primera (que casi todos definirían como O (n)). No son directamente comparables.

La primera solución podría ser preferible en pequeños conjuntos de datos. Pero si nuestro conjunto de datos es muy grande (por ejemplo, contiene la mayor parte del rango permitido de entradas), podríamos preferir el segundo.

¿Existe un algoritmo mejor que o (n) para el siguiente problema, dado que un hashset contiene enteros y un número, encuentra el número más cercano al número dado?

¿Cómo puede haberlo?

Un hashset es excelente para hacer la pregunta “¿Existe este valor?” No proporciona ningún tipo de soporte para “Encontrar algo parecido a este valor”. Eso significa que si tiene que responder a esta pregunta y no Afortunadamente, su valor está realmente en el hashset, absolutamente tiene que hacer algo con todos los valores. Eso significa que no estás hablando mejor que O (n).

Ahora, si tenía un montón (m) de valores que está buscando, es posible que pueda hacerlo mejor que O (m * n). Una tabla hash no es una buena estructura para responder esta pregunta, pero podría responderla en tiempo O (log n) en una matriz ordenada, por ejemplo. Pero poner todos los datos en la matriz ordenada significa que tendría que ordenar los elementos, lo que es peor que una operación O (n). Si m es lo suficientemente grande, puede valer la pena hacerlo.