O (1) hash ups?

Question

Me encontré con una afirmación de que HashSet <T> .Contains() es una operación O (1). Esto me sorprendió ya que cada discusión de hashing que he encontrado menciona la posibilidad de colisiones, lo que potencialmente puede llevar a O (n) tiempo de ejecución.

Siendo curioso, miré en la documentación para HashSet <T> .Contiene y también HashTable.Contains. La documentación de ambos métodos hace el mismo reclamo.

Cuando miro en el reflector, HashSet <T> .Contains() se implementa con un bucle for, pasando por una lista de ranuras que contienen valores que tienen el mismo hash.

Ahora bien, esas mismas discusiones de hashing también han mencionado que un buen algoritmo hashing evita colisiones y en esas circunstancias la búsqueda será de hecho O (1). Pero mi comprensión de la notación Big O es que es el peor tiempo de ejecución, no el mejor.

¿El reclamo O (1) es incorrecto? ¿O me estoy perdiendo algo?

Answer 1

Pero mi comprensión de la notación Big O es que es el peor tiempo de ejecución, no el mejor.

Lamentablemente, no existe un "estándar" para Big-O al describir algoritmos. A menudo, se usa para describir el caso general o promedio, no el peor de los casos.

De Wikipedia:

... esta notación es ahora con frecuencia también se utiliza en el análisis de algoritmos para describir el uso de un algoritmo de cálculo de los recursos: el peor de los casos, o caso promedio ...

En este caso, está describiendo un caso estándar, dado el hashing correcto. Si tiene hash adecuado en su lugar, el comportamiento limitante será constante para el tamaño N, por lo tanto O (1).

Answer 2

En general, es O (1).

Answer 3

No, Big O no define "el peor de los casos", sino que define un límite. Las búsquedas basadas en hash (con buenos algoritmos hash que proporcionan una distribución de valor eficiente y una baja tasa de colisión) progresan hacia un valor constante a medida que aumenta el número de elementos (nunca alcanzarán ese valor constante, pero ese es el límite.)

Answer 4

Creo que significa O (1) en promedio.

Answer 5

Mi comprensión de Big Oh es que el "peor caso" generalmente se refiere a la cantidad de elementos involucrados. Entonces, si una función fuera a realizar O (n) con 10 elementos, pero O (n al cuadrado) con 100 o más (no estoy seguro de que tal algoritmo realmente exista), entonces el algoritmo se considera O (n al cuadrado).

Answer 6

O (1) no significa necesariamente "el peor de los casos". Para los hashes, uno generalmente dice que el tiempo de búsqueda "esperado" es O (1), ya que la probabilidad de colisiones hash es pequeña.

Answer 7

Para una tabla hash correctamente implementada, las búsquedas tienen amortized complejidad de tiempo constante.

En la práctica, una sola consulta puede ser O (n) en caso de colisión, como dices. Sin embargo, si realiza una gran cantidad de búsquedas, la complejidad de tiempo promedio por operación es constante.

Wikipedia postular:

análisis amortizado se diferencia de rendimiento en el caso promedio en que la probabilidad no está involucrado; el análisis amortizado garantiza el tiempo por operación sobre el peor de los casos.

El método requiere el conocimiento de qué serie de operaciones son posibles. Este suele ser el caso con las estructuras de datos, que tienen un estado que persiste entre las operaciones. La idea básica es que una operación en el peor de los casos puede alterar el estado de tal manera que el peor de los casos no puede volver a ocurrir durante mucho tiempo, lo que "amortiza" su costo.

Answer 8

No, la notación Big-O no está necesariamente restringida al peor de los casos. En general, verá publicado Big-O para el mejor de los casos, el promedio de casos y el peor de los casos. Es solo que la mayoría de la gente tiende a enfocarse en el peor de los casos. Excepto en el caso de una tabla hash, el peor de los casos rara vez ocurre, por lo que usar el caso promedio tiende a ser más útil.

Sí, una buena función de reducción reduce la probabilidad de una colisión. Una mala función de hash puede causar el efecto de agrupamiento (donde los valores de hash diferentes al mismo valor exacto o cerca del mismo valor). Es fácil demostrar que HashSet puede convertirse en O (n) implementando la función GetHashCode de tal manera que devuelve el mismo valor todo el tiempo.

En un nutshull, sí HashSet y Dictionary se puede describir como que tiene O (1) la complejidad en tiempo de ejecución debido a que el énfasis está en el escenario de caso medio.

Por cierto, Big-O también se puede utilizar para analizar la complejidad amortizada. La complejidad amortizada es cómo se comporta una secuencia de operaciones separadas (ya veces incluso diferentes) cuando se agrupan juntas como si fueran una gran operación. Por ejemplo, se dice que un árbol splay ha amortizado O (log (n)) búsqueda, inserción y eliminación de complejidad incluso si el peor caso para cada uno podría O (n) y el mejor de los casos es O (1).

Answer 9

Las tablas hash no solo tienen un rendimiento de caja promedio O (1), pero si la función hash es aleatoria, para cualquier porcentaje dado P < 100%, el rendimiento que puede obtenerse P% de las veces el cuento de hadas diseñado es O (1). Aunque los casos parasitarios extremos se vuelven cada vez más severos a medida que aumenta el N, eso se equilibra con el hecho de que incluso los casos moderadamente parasitarios se vuelven cada vez menos probables.