🧱 Arreglos

init

Pruébalo: Toca leer para hacer parpadear un índice (verde = O(1)). Luego inserta en un índice temprano y observa cómo las celdas de la derecha se desplazan en cascada hacia el naranja — ese es el costo O(n) hecho visible.

Por qué importa

Los arreglos son la estructura de datos más fundamental de la computación. Cualquier otra estructura de datos está construida sobre arreglos o diseñada para superar sus limitaciones. Entender los arreglos significa entender cómo las computadoras realmente almacenan y acceden a los datos.

La idea

Imagina una fila de casilleros numerados en un pasillo. Cada casillero tiene un número (índice) pintado en él, y puedes caminar al instante hasta el casillero #47 porque sabes exactamente dónde está — no necesitas revisar primero los casilleros del 1 al 46.

Eso es un arreglo. Un bloque contiguo de memoria donde cada ranura tiene una posición fija.

La magia: como los elementos se almacenan uno al lado del otro, acceder a cualquier elemento por su índice es instantáneo — O(1). La computadora calcula: dirección_base + (índice * tamaño_del_elemento).

La limitación: si quieres insertar un nuevo elemento en el medio, todo lo que viene después debe desplazarse — O(n). Como insertar un libro en un estante muy apretado.

Puntos clave

• El acceso por índice es O(1) — la fortaleza que define a los arreglos
• La inserción/eliminación en posiciones arbitrarias es O(n) debido al desplazamiento
• La memoria es contigua — excelente para el rendimiento de la caché
• El tamaño suele ser fijo; los arreglos dinámicos amortizan los costos de redimensionamiento

Profundizando

Los arreglos brillan cuando necesitas acceso aleatorio y rara vez insertas/eliminas en el medio. Los arreglos dinámicos (Vec, ArrayList) manejan el redimensionamiento duplicando la capacidad cuando se llenan — esto hace que el costo amortizado de agregar siga siendo O(1). Los arreglos también son amigables con la caché: acceder a elementos secuenciales es rápido porque se cargan juntos en la caché de la CPU.

Por qué O(1) "amortizado" — la prueba de la duplicación

Un arreglo dinámico comienza con cierta capacidad pequeña (digamos 4) y se duplica cada vez que se llena. La mayoría de las llamadas a push simplemente escriben en una ranura libre — O(1). Pero de vez en cuando, llenas el arreglo y tienes que asignar uno nuevo del doble de tamaño y copiar n elementos — eso es O(n).

Entonces, ¿push es realmente O(1)? En promedio, a lo largo de muchas inserciones, sí. Cuenta el trabajo total para crecer de 1 a n elementos:

copias: 1 + 2 + 4 + 8 + … + n/2 + n
     = 2n − 1
     = O(n) de trabajo total repartido entre n inserciones
     = O(1) por inserción, amortizado

La suma geométrica duplica cada término, pero los términos previos se reducen a la mitad. El trabajo total se mantiene lineal en n. Si reduces a la mitad en lugar de duplicar, cada redimensionamiento es O(n) y no obtienes el beneficio de la amortización — el trabajo total sube a O(n²). La duplicación es la constante mágica que hace cuadrar las cuentas.

Este es el primer contacto canónico con el análisis amortizado — el mismo patrón aparece en el rehashing de tablas hash, la construcción de montículos y las colas con buffer circular.

Localidad de caché — la razón de un orden de magnitud

Los arreglos no son rápidos solo por el acceso O(1) — son rápidos porque las CPU modernas prebuscan (prefetch) memoria secuencial. Cuando lees arr[i], la CPU carga una línea de caché completa (típicamente 64 bytes — 16 enteros, u 8 dobles) en la caché L1. Leer luego arr[i+1] y después arr[i+2] son aciertos de caché gratuitos.

Una lista enlazada con los mismos datos dispersos por la memoria paga un fallo de L1 en la mayoría de las desreferencias de punteros. Las constantes:

• Acierto en L1: ~1 ns (≈ 4 ciclos de CPU)
• Acierto en L2: ~3 ns
• Acierto en L3: ~10 ns
• Memoria principal: ~100 ns

En un bucle caliente, un arreglo puede ser de 10 a 100× más rápido que una lista enlazada que contenga los mismos elementos, aunque ambos sean O(n) para recorrer. Big-O oculta esto. La regla práctica en robótica: prefiere arreglos de estructuras (AoS) o estructura de arreglos (SoA) para cualquier bucle interno; reserva las listas enlazadas para el raro caso en que necesites un empalme (splice) O(1) con una referencia a un nodo activo.

Detalles matemáticos

Complejidad temporal

Access: O(1)

Search (unsorted): O(n)

Insert at end: O(1) amortized

Insert at index i: O(n-i)

Cálculo de dirección

address[i] = base + i × sizeof(element)

Implementación

Arreglo en Rust

// Arreglo de tamaño fijo
let arr: [i32; 5] = [1, 2, 3, 4, 5];
let third = arr[2]; // acceso O(1)

// Arreglo dinámico (Vec)
let mut vec = Vec::new();
vec.push(1); // O(1) amortizado
vec.insert(0, 0); // O(n) - desplaza todos los elementos

Operaciones clave

• arr[i] - acceso aleatorio O(1)
• vec.push(x) - agregado O(1) amortizado
• vec.insert(i, x) - inserción O(n)
• vec.remove(i) - eliminación O(n)

Práctica

Tres problemas clásicos construidos sobre arreglos, cada uno mostrando una técnica diferente:

• Two Sum — fácil · cambiar memoria por tiempo usando una tabla hash
• Subarreglo máximo (Kadane) — medio · estado acumulado en una sola pasada
• Atrapar agua de lluvia — difícil · recorrido con dos punteros y máximos acumulados

→ Explora todos los problemas de práctica