Establecer el tiempo y la complejidad de la velocidad

Estoy revisando los algoritmos y las estructuras de datos y tengo algunas preguntas, así como las declaraciones que me gustaría que verifique.Establecer el tiempo y la complejidad de la velocidad

ArrayList - O (1) (tamaño, obtención, configuración, ...), O (n) - add operation.
LinkedList - todas las operaciones O (1) (incluido add()), excepto para recuperar n-ésimo elemento que es O (n). Supongo que la operación size() también se ejecuta en O (1), ¿verdad?

TreeSet - todas las operaciones O (lg (N)). La operación size() toma O (lg (n)), ¿verdad?

HashSet - todas las operaciones O (1) si se aplica la función de hash adecuada.
HashMap - todas las operaciones O (1), anólogas a HashSet.

Cualquier otra explicación es muy bienvenida. Gracias de antemano.

Fuente

2011-07-09 Anton K.

Si usted tiene tal HashSet magia, ¿por qué necesita ArrayList? –

@Stas: Porque una Lista y un Conjunto no son lo mismo, y también porque los factores constantes aún pueden ser significativamente diferentes ... –

@Stas: El orden solo le da una idea de cómo se escala la operación. No le dirá el factor, p. HashSet puede ser mucho más lento que ArrayList y no tiene los métodos get()/set(). –

ArrayList.add() es amortizado O (1). Si la operación no requiere un cambio de tamaño, es O (1). Si es si requieren un cambio de tamaño, es O (n), pero el tamaño se aumenta de tal manera que el siguiente cambio de tamaño no se producirá durante un tiempo.

Desde el Javadoc:

La operación de adición se ejecuta en tiempo constante amortizado, es decir, la adición de n elementos requiere tiempo O (n). Todas las otras operaciones se ejecutan en tiempo lineal (aproximadamente hablando). El factor constante es bajo comparado con el de la implementación LinkedList.

La documentación es generalmente bastante buena para las colecciones de Java, en términos de análisis de rendimiento.

El O (1) para los algoritmos hash no es solo cuestión de aplicar una función hash "adecuada": incluso con una muy buena función hash, aún podría obtener colisiones hash. La habitual complejidad es O (1), pero por supuesto puede ser O (n) si todos los hashes chocan.

Fuente

2011-07-09 13:02:23

+1: Del mismo modo, LinkedList es O (1) siempre que no active un GC, que es más probable que lo haga. ;) –

"no activa un GC"? –

@Suraj: GC = "recolección de basura" (?) – abeln

Visite los siguientes enlaces. Te ayudará a aclarar tus dudas.

Fuente

2011-07-09 13:13:58

Establecer el tiempo y la complejidad de la velocidad

Respuesta

Cuestiones relacionadas