¿Complejidad de búsqueda de HashSet?

Una operación de búsqueda O contains para uno solo puede ser O(n) en el peor de los casos, ¿verdad? Por lo tanto, para elementos n buscar en hashSet será O(n^2)?¿Complejidad de búsqueda de HashSet?

Fuente

2011-07-04 phoenix

¿Qué quiere decir con "for n elements" exactamente? ¿Realizando una búsqueda de cada elemento? Tenga en cuenta que, aunque el peor de los casos es O (n), por lo general es O (1). –

Sí, pero en realidad es el peor de los casos: si todos los elementos de la HashSet tienen el mismo código hash (o un código hash que lleva a el mismo cubo). Con un hashCode correctamente escrito y una muestra de clave normalmente distribuida, una búsqueda es O (1).

Fuente

2011-07-04 18:27:39

-18

lookp toma O (c)

c = valor constante

Fuente

2011-07-04 18:27:05

Sí, pero la razón por la que tenemos HashSets es que encontramos este peor caso con muy, muy baja probabilidad, y suele ser mucho más rápido que el nlogn garantizado para un montón o un TreeSet (autoequilibrado) o el garantizado n^2 para una lista desordenada.

Fuente

2011-07-04 19:08:50 krasnerocalypse

¿Complejidad de búsqueda de HashSet?

Respuesta

Cuestiones relacionadas