Tiempo de ejecución para insertar n elementos en una tabla hash vacía

Question

La gente dice que se necesita amortizar O (1) para colocarlo en una tabla hash. Por lo tanto, poner n elementos debe ser O (n). Sin embargo, eso no es cierto para n grande, ya que, como dijo el contestador, " Todo lo que necesita para satisfacer el O (1) amortizado esperado es expandir la tabla y repetir todo con una nueva función aleatoria de hash cada vez que se produzca una colisión. & Quot ;

Entonces: ¿cuál es el tiempo de ejecución promedio para insertar n elementos en una tabla hash? Me doy cuenta de que esto depende probablemente de la implementación, así que menciona de qué tipo de implementación estás hablando.

Por ejemplo, si hay (registro n) colisiones igualmente espaciadas, y cada colisión requiere O (k) para resolver, donde k es el tamaño actual de la tabla hash, entonces tendrías esta relación de recurrencia:

T(n) = T(n/2) + n/2 + n/2

(es decir, te tomas el tiempo para insertar n / 2 elementos, luego tienes una colisión, tomas n / 2 para resolver, luego haces los n / 2 inserciones restantes sin una colisión). Esto todavía termina siendo O (n), así que sí. Pero, ¿es esto razonable?

Answer 1

Depende completamente de lo ineficiente que sea tu repetición. Específicamente, si puede estimar correctamente el tamaño esperado de su tabla hash la segunda vez, su tiempo de ejecución aún se aproxima a O (n). Efectivamente, debe especificar qué tan ineficiente es el cálculo del tamaño de la recarga antes de poder determinar el orden esperado.

Answer 2

  

La gente dice que se necesita amortizar O (1) para colocarlo en una tabla hash.

Desde un punto de vista teórico, es esperado amortizado O (1).

Las tablas hash son fundamentalmente una estructura de datos aleatorizada, en el mismo sentido que quicksort es un algoritmo aleatorio. Necesita generar sus funciones hash con cierta aleatoriedad, o de lo contrario existen entradas patológicas que no son O (1).

Puede lograr el O (1) amortizado esperado usando hashing dinámico perfecto :

La idea ingenua que originalmente publiqué fue repetir con una nueva función aleatoria aleatoria en cada colisión. (Vea también funciones hash perfectas ) El problema con esto es que esto requiere O (n ^ 2 ) espacio, desde la paradoja del cumpleaños.

La solución es tener dos tablas hash, con la segunda tabla para colisiones; resuelva las colisiones en esa segunda tabla reconstruyéndola. Esa tabla tendrá elementos O (\ sqrt {n}), por lo que crecerá a tamaño O (n).

En la práctica, a menudo solo usas una función hash fija porque puedes asumir (o no te importa si) tu entrada es patológica, al igual que lo haces a menudo sin una asignación previa de datos al azar.

Answer 3

Todo lo que O (1) está diciendo es que la operación se realiza en tiempo constante, y que no depende de la cantidad de elementos en su estructura de datos.

En palabras simples, esto significa que tendrá que pagar el mismo costo, sin importar qué tan grande sea su estructura de datos.

En términos prácticos, esto significa que las estructuras de datos simples, como los árboles, son generalmente más efectivas cuando no tiene que almacenar una gran cantidad de datos. En mi experiencia, encuentro árboles más rápidos hasta ~ 1k elementos (enteros de 32 bits), luego las tablas hash se hacen cargo. Pero como de costumbre YMMW.

Answer 4

¿Por qué no solo ejecutar algunas pruebas en su sistema? Tal vez si publica la fuente, podemos volver y probarlos en nuestros sistemas y realmente podríamos convertir esto en una discusión muy útil.

Simplemente no es la implementación, sino también el entorno el que decide cuánto tiempo tarda realmente el algoritmo. Sin embargo, puede ver si hay alguna muestra de evaluación comparativa disponible o no. El problema con la publicación de mis resultados no servirá de nada, ya que la gente no tiene idea de qué más se está ejecutando en mi sistema, cuánta memoria RAM es libre ahora y así sucesivamente. Solo puedes tener una idea amplia. Y eso es tan bueno como lo que te da la gran O.