Complejidad y Rendimiento de Estructuras de Datos

La elección de la estructura de datos adecuada es la decisión de diseño con mayor impacto en el rendimiento de un sistema de software. Una estructura inapropiada puede degradar un algoritmo de tiempo constante $O(1)$ a cuadrático $O(n^2)$ .

1. Tabla Maestra de Complejidad Asintótica #

Estructura de Datos	Acceso por Índice	Búsqueda por Valor	Inserción (Medio / Peor)	Borrado (Medio / Peor)	Complejidad Espacial
Array Estático	$O(1)$	$O(n)$	N/A (Tamaño fijo)	N/A (Tamaño fijo)	$O(n)$
Array Dinámico (`ArrayList`, `vector`)	$O(1)$	$O(n)$	$O(1)$ amortizado / $O(n)$	$O(n)$	$O(n)$
Lista Enlazada (`LinkedList`)	$O(n)$	$O(n)$	$O(1)$ (en extremos)	$O(1)$ (con nodo conocido)	$O(n)$
Tabla Hash (`HashMap`, `dict`)	N/A (Clave-Valor)	$O(1)$ medio / $O(n)$ peor	$O(1)$ medio / $O(n)$ peor	$O(1)$ medio / $O(n)$ peor	$O(n)$
Árbol Binario Balanceado (`TreeMap`, AVL)	N/A	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Montículo Binario (`PriorityQueue`)	$O(1)$ (mín/máx)	$O(n)$	$O(\log n)$	$O(\log n)$ (extracción)	$O(n)$

2. Array Dinámico vs Lista Enlazada: La Realidad de la Caché #

En teoría clásica, una LinkedList inserta al inicio en $O(1)$ mientras que un ArrayList requiere desplazar elementos ( $O(n)$ ). Sin embargo, en hardware moderno:

Array Dinámico (Memoria Contigua): Los elementos residen en bloques contiguos de RAM, lo que permite a la CPU precargar líneas de caché L1/L2 completas (Hardware Prefetching).
Lista Enlazada (Memoria Fragmentada): Cada nodo es un objeto independiente disperso en el Heap con punteros extra (prev, next), provocando continuos fallos de caché (Cache Misses).

Regla Práctica: En el 95% de los escenarios del mundo real, un array dinámico supera en velocidad a una lista enlazada debido a la localidad espacial.

3. Tablas Hash y Gestión de Colisiones #

Las tablas Hash alcanzan tiempo promedio $O(1)$ convirtiendo la clave en un índice numérico mediante una función hash:

Factor de Carga (Load Factor): Relación entre el número de elementos y el tamaño de la tabla (típicamente 0.75). Al superarse, la tabla se redimensiona (rehashing al doble de tamaño).
Estrategias de Resolución de Colisiones:
- Encadenamiento Separado (Separate Chaining): Cada celda contiene una lista enlazada o un árbol rojo-negro (utilizado en Java 8+ cuando una celda supera 8 colisiones).
- Direccionamiento Abierto (Open Addressing): Búsqueda lineal o cuadrática del siguiente hueco libre en el array contiguo (utilizado en Python dict).

Resumen del tema

Conceptos clave #

Compromiso Acceso vs Inserción: los arrays ofrecen acceso $O(1)$ por índice; los árboles mantienen el orden en $O(\log n)$ ; las tablas hash ofrecen búsqueda y escritura en $O(1)$ promedio.
Localidad de Caché: la memoria contigua de los arrays dinámicos supera habitualmente la flexibilidad teórica de los punteros en listas enlazadas.
Factor de Carga y Rehashing: una tabla hash mal dimensionada o con una función hash deficiente puede degradar sus operaciones a $O(n)$ .

Qué debes recordar #

Usa arrays contiguos como opción predeterminada, tablas hash para búsquedas clave-valor rápidas y árboles balanceados cuando necesites mantener el orden de los elementos.

1. Tabla Maestra de Complejidad Asintótica #

Estructura de Datos

Acceso por Índice

Búsqueda por Valor

Inserción (Medio / Peor)

Borrado (Medio / Peor)

Complejidad Espacial

Array Estático

O(1)

O(n)

N/A (Tamaño fijo)

O(n)

Array Dinámico (ArrayList, vector)

O(1)

O(n)

O(1)

amortizado /

O(n)

O(n)

O(n)

Lista Enlazada (LinkedList)

O(n)

O(n)

O(1)

(en extremos)

O(1)

(con nodo conocido)

O(n)

Tabla Hash (HashMap, dict)

N/A (Clave-Valor)

O(1)

medio /

O(n)

peor

O(1)

medio /

O(n)

peor

O(1)

medio /

O(n)

peor

O(n)

Árbol Binario Balanceado (TreeMap, AVL)

N/A

O(\log n)

O(\log n)

O(\log n)

O(n)

Montículo Binario (PriorityQueue)

O(1)

(mín/máx)

O(n)

O(\log n)

O(\log n)

(extracción)

O(n)

2. Array Dinámico vs Lista Enlazada: La Realidad de la Caché #

En teoría clásica, una LinkedList inserta al inicio en

O(1)

mientras que un ArrayList requiere desplazar elementos (

O(n)

). Sin embargo, en hardware moderno:

Array Dinámico (Memoria Contigua): Los elementos residen en bloques contiguos de RAM, lo que permite a la CPU precargar líneas de caché L1/L2 completas (Hardware Prefetching).

Lista Enlazada (Memoria Fragmentada): Cada nodo es un objeto independiente disperso en el Heap con punteros extra (prev, next), provocando continuos fallos de caché (Cache Misses).

Regla Práctica: En el 95% de los escenarios del mundo real, un array dinámico supera en velocidad a una lista enlazada debido a la localidad espacial.

3. Tablas Hash y Gestión de Colisiones #

Las tablas Hash alcanzan tiempo promedio

O(1)

convirtiendo la clave en un índice numérico mediante una función hash:

Factor de Carga (Load Factor): Relación entre el número de elementos y el tamaño de la tabla (típicamente 0.75). Al superarse, la tabla se redimensiona (rehashing al doble de tamaño).

Estrategias de Resolución de Colisiones:

Encadenamiento Separado (Separate Chaining): Cada celda contiene una lista enlazada o un árbol rojo-negro (utilizado en Java 8+ cuando una celda supera 8 colisiones).
Direccionamiento Abierto (Open Addressing): Búsqueda lineal o cuadrática del siguiente hueco libre en el array contiguo (utilizado en Python dict).

Resumen del tema

Conceptos clave #

Compromiso Acceso vs Inserción: los arrays ofrecen acceso $O(1)$ por índice; los árboles mantienen el orden en $O(\log n)$ ; las tablas hash ofrecen búsqueda y escritura en $O(1)$ promedio.
Localidad de Caché: la memoria contigua de los arrays dinámicos supera habitualmente la flexibilidad teórica de los punteros en listas enlazadas.
Factor de Carga y Rehashing: una tabla hash mal dimensionada o con una función hash deficiente puede degradar sus operaciones a $O(n)$ .

Qué debes recordar #

Usa arrays contiguos como opción predeterminada, tablas hash para búsquedas clave-valor rápidas y árboles balanceados cuando necesites mantener el orden de los elementos.

Complejidad y Rendimiento de Estructuras de Datos

1. Tabla Maestra de Complejidad Asintótica #

2. Array Dinámico vs Lista Enlazada: La Realidad de la Caché #

3. Tablas Hash y Gestión de Colisiones #

Conceptos clave #

Qué debes recordar #

Quiz: Complejidad y Rendimiento de Estructuras de Datos

Complejidad y Rendimiento de Estructuras de Datos

1. Tabla Maestra de Complejidad Asintótica #

2. Array Dinámico vs Lista Enlazada: La Realidad de la Caché #

3. Tablas Hash y Gestión de Colisiones #

Conceptos clave #

Qué debes recordar #

Quiz: Complejidad y Rendimiento de Estructuras de Datos