Sesión 02: Grokking Algorithms (Capítulo 1, Parte 2) + CTCI (Big O) — Complejidad Temporal y Espacial#

Navegación rápida:

• ← Sesión 01: Búsqueda Binaria y Logaritmos
• Sesión 03: Memoria, Arrays y Strings →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 45-60 minutos.
• Código fuente compilado y probado: practica-rust/dia_02.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Antes de analizar algoritmos, necesitamos un lenguaje matemático riguroso pero intuitivo. Consulta el Glosario Maestro para profundizar.

Notación Big O (O)#

• (a) En palabras simples (intuición): Es una etiqueta que te dice cómo "envejece" o qué tan rápido se cansa tu programa cuando le arrojas montañas de datos. No mide los segundos de un cronómetro, sino la curva de crecimiento del esfuerzo.
• (b) Definición técnica paso a paso: Notación asintótica que establece una cota superior formal sobre el número de operaciones de CPU o uso de memoria cuando el tamaño de la entrada N tiende a infinito: f(N) = O(g(N)) ⟺ ∃ c > 0, N₀ ≥ 0 tal que |f(N)| ≤ c · |g(N)| ∀ N ≥ N₀.
• (c) Cómo funciona en Rust (memoria y tipos): Las estructuras de datos de Rust reflejan directamente su Big O: indexar un slice &[T] es O(1) directo por aritmética de punteros en Stack; insertar al final de un Vec<T> es O(1) amortizado; mientras que insertar al inicio con vec.insert(0, val) es O(N) porque debe desplazar todos los bytes contiguos en el Heap mediante memmove.
• (d) Error típico de Junior: Cronometrar una función en su laptop usando Instant::now() con un arreglo pequeño de 10 elementos y asumir que un algoritmo O(N²) es "rápido" porque tardó 2 microsegundos.

Complejidad Espacial Auxiliar (Auxiliary Space Complexity)#

• (a) En palabras simples (intuición): La cantidad de cuadernos extra o espacio de escritorio temporal que necesitas para hacer los cálculos, sin contar los datos originales que te entregó el usuario.
• (b) Definición técnica paso a paso: Mide la memoria adicional requerida por el algoritmo durante su ejecución, excluyendo la memoria que ocupan los datos de entrada originales. Comprende la memoria en el Stack (marcos de funciones) y en el Heap (asignaciones dinámicas de buffers, tablas o nodos).
• (c) Cómo funciona en Rust (memoria y tipos): Si una función recibe nums: &[i32], esos N enteros ya viven en memoria. Si la función crea variables locales escalares (let mut sum = 0;), el espacio auxiliar es O(1). Si crea un Vec::with_capacity(nums.len()), el espacio auxiliar es O(N) en el Heap.
• (d) Error típico de Junior: Olvidar que la recursión consume memoria en el Stack: una función recursiva que llama a sí misma N veces tiene complejidad espacial O(N), aunque no cree listas ni vectores en el Heap.

Stack (Pila de Ejecución) vs Heap (Montículo de Memoria)#

• (a) En palabras simples (intuición): El Stack es una pila de platos limpios: súper rápida y ordenada; solo puedes poner un plato arriba o quitar el último. El Heap es un almacén gigante con estanterías numeradas: puedes pedir cualquier tamaño de caja cuando quieras, pero buscar espacio libre y acomodarlo toma más tiempo.
• (b) Definición técnica paso a paso: El Stack es un segmento de memoria contiguo gestionado directamente por el puntero de pila de la CPU (RSP en x86_64). Asignar memoria cuesta literalmente una sola instrucción de suma o resta (sub rsp, bytes). El Heap es una región dinámica gestionada por el asignador del sistema operativo (system allocator / jemalloc), donde los bloques pueden solicitarse en tamaños variables en tiempo de ejecución.
• (c) Cómo funciona en Rust (memoria y tipos): Los tipos de tamaño conocido en compilación (i32, usize, punteros directos) viven en el Stack. Los contenedores dinámicos como Vec<T>, String y Box<T> almacenan un descriptor de 24 bytes en el Stack (ptr, cap, len) y reservan los datos reales en el Heap. Al salir del ámbito (scope), el destructor Drop de Rust libera automáticamente el Heap sin necesidad de Garbage Collector.
• (d) Error típico de Junior: Creer que llamar a clone() en un Vec o String es una operación barata O(1), cuando en realidad reserva un nuevo bloque en el Heap y copia todos los elementos en O(N).

Marco de Activación (Stack Frame)#

• (a) En palabras simples (intuición): Una cajita que la CPU guarda cada vez que llamas a una función, conteniendo sus variables locales, argumentos y la dirección exacta de retorno para saber a dónde volver cuando termine.
• (b) Definición técnica paso a paso: Estructura de datos generada en el Stack en cada llamada a subrutina según la convención de llamadas (calling convention). Almacena los argumentos pasados, la dirección de retorno de instrucción (RIP), el puntero base del marco (RBP) y las variables locales.
• (c) Cómo funciona en Rust (memoria y tipos): El tamaño de cada Stack Frame es fijado estáticamente por el compilador. En arquitecturas modernas, el tamaño de la pila de un hilo suele ser de 2 MB a 8 MB. Si una función recursiva genera 300,000 llamadas anidadas, agota la memoria del Stack y el sistema operativo aborta el proceso de inmediato por Stack Overflow.
• (d) Error típico de Junior: Asumir que una recursión profunda puede sustituir siempre a un bucle while sin considerar el límite físico de la pila.

Costo Amortizado (Amortized Cost)#

• (a) En palabras simples (intuición): Como comprar una membresía de gimnasio anual. Pagas una suma fuerte un solo día, pero prorrateado entre los 365 días del año, el costo diario es prácticamente nada.
• (b) Definición técnica paso a paso: Promedio formal del costo de una operación sobre una secuencia larga de operaciones en el peor caso. Una operación infrecuente y muy costosa es compensada por una gran cantidad de operaciones extremadamente rápidas.
• (c) Cómo funciona en Rust (memoria y tipos): Vec::push tiene costo O(1) amortizado. La mayoría de los push solo escriben en el Heap en un slot preasignado (O(1)). Cuando la capacidad se llena, el vector reubica la memoria (realloc), duplicando su tamaño y copiando todos los N elementos previos (O(N)). Como esto ocurre con una frecuencia geométrica decreciente (1, 2, 4, 8, 16...), el costo por inserción promedio sigue siendo matemáticamente O(1).
• (d) Error típico de Junior: Creer que cada push individual tiene tiempo garantizado estrictamente constante de microsegundos, o no usar Vec::with_capacity(n) cuando ya se conoce el tamaño total previo.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

¿Por Qué la Medición en Segundos no Sirve para Evaluar Algoritmos?#

Si mides un algoritmo con un cronómetro:

1. En un procesador Intel Core i9 de 5.8 GHz completará el trabajo mucho antes que en un microcontrolador de 50 MHz.
2. Si el sistema operativo decide interrumpir el hilo para atender la tarjeta de red o un proceso en segundo plano, la lectura se distorsiona.
3. La temperatura del procesador puede activar el thermal throttling reduciendo la frecuencia a la mitad.

La informática teórica abstrae estos factores físicos midiendo el número de instrucciones elementales en función del tamaño de entrada N.

Las Tres Reglas de Oro de Big O#

Regla 1: Descartar las Constantes Multiplicativas#

Si un algoritmo realiza dos pasadas completas independientes sobre un arreglo de tamaño N:

¿Por qué descartamos el 2? Porque conforme N crece hacia millones, la forma de la curva es idéntica a una línea recta. Si N se multiplica por 10, el tiempo se multiplica por 10. Las constantes afectan el rendimiento absoluto en microsegundos, pero no la ley física de escalabilidad.

Regla 2: Descartar Términos No Dominantes#

Si una función tiene un bloque con dos bucles anidados (N²) y luego un bucle simple (N):

Comparemos los valores cuando N = 10,000:

• N² = 100,000,000 operaciones.
• 100N = 1,000,000 operaciones (apenas el 1% del total).
• $500$ operaciones (el 0.0005% del total).

A medida que N crece, el término de mayor exponente aplasta a los términos menores hasta volverlos matemáticamente insignificantes.

Regla 3: Suma vs Multiplicación#

• Suma (O(A + B)): Cuando ejecutas una tarea tras otra de forma secuencial.

  for item in list_a { /* O(A) */ }
  for item in list_b { /* O(B) */ }
  // Total: O(A + B)

• Multiplicación (O(A × B)): Cuando por cada elemento de una colección, iteras exhaustivamente sobre otra.

  for item_a in list_a {
      for item_b in list_b { /* O(A * B) */ }
  }
  // Total: O(A * B)

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Jerarquía de Crecimiento Asintótico#

Consulta el diagrama de arquitectura y curvas de complejidad:

• Gráfico SVG: ![Visualización del Día 02 y Memoria en Rust](../diagrams/sesiones/dia_02.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart LR
    O1["O(1) Constante"] --> OL["O(log N) Logarítmico"]
    OL --> ON["O(N) Lineal"]
    ON --> ONL["O(N log N) Linealítmico"]
    ONL --> ON2["O(N²) Cuadrático"]
    ON2 --> O2N["O(2^N) Exponencial"]
    O2N --> ONF["O(N!) Factorial"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Caso 1: Consumo Espacial en Recursión (recursive_countdown_stack(3))#

Cada llamada recursiva añade un marco de pila. La memoria del hilo crece linealmente con N:

INICIO: LLAMADA A recursive_countdown_stack(3)
+-------------------------------------------------------------+
| Marco 3: recursive_countdown_stack(n = 3)                   |
| Dirección: 0x7FFF_0100 | Argumento n: 3 | Retorno: caller   |
+-------------------------------------------------------------+
                              |
                              v Invocación interna (n - 1)
+-------------------------------------------------------------+
| Marco 2: recursive_countdown_stack(n = 2)                   |
| Dirección: 0x7FFF_00B0 | Argumento n: 2 | Retorno: Marco 3  |
+-------------------------------------------------------------+
| Marco 3: recursive_countdown_stack(n = 3)                   |
| Dirección: 0x7FFF_0100 | Argumento n: 3 | Retorno: caller   |
+-------------------------------------------------------------+
                              |
                              v Invocación interna (n - 1)
+-------------------------------------------------------------+
| Marco 1: recursive_countdown_stack(n = 1)                   |
| Dirección: 0x7FFF_0060 | Argumento n: 1 | Retorno: Marco 2  |
+-------------------------------------------------------------+
| Marco 2: recursive_countdown_stack(n = 2)                   |
| Dirección: 0x7FFF_00B0 | Argumento n: 2 | Retorno: Marco 3  |
+-------------------------------------------------------------+
| Marco 3: recursive_countdown_stack(n = 3)                   |
| Dirección: 0x7FFF_0100 | Argumento n: 3 | Retorno: caller   |
+-------------------------------------------------------------+
                              |
                              v Caso base (n = 0) -> Desapilado
Pico máximo de memoria Stack: 3 marcos = O(N) espacio auxiliar.

Caso 2: Consumo Espacial en Bucle Iterativo (iterative_countdown_memory(3))#

Un único marco de pila se reutiliza indefinidamente. El puntero de pila permanece quieto:

EJECUCIÓN DEL BUCLE ITERATIVO
+-------------------------------------------------------------+
| Marco único: iterative_countdown_memory                     |
| Dirección: 0x7FFF_0100                                      |
| Variable local `count`: mutada en el registro de la CPU     |
| Iteración 1: count = 1                                      |
| Iteración 2: count = 2                                      |
| Iteración 3: count = 3                                      |
+-------------------------------------------------------------+
Pico máximo de memoria Stack: 1 marco constante = O(1) espacio auxiliar.

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (practica-rust/dia_02.rs)#

//! Implementación canónica de funciones representativas de Big O en Rust.
//! Compilable y verificable con `rustc --test`.

/// O(1) tiempo, O(1) espacio: Acceso inmediato por dirección de memoria.
pub fn get_first_element(nums: &[i32]) -> Result<i32, &'static str> {
    nums.first().copied().ok_or("Slice cannot be empty")
}

/// O(log N) tiempo, O(1) espacio: El espacio numérico se divide sucesivamente entre 2.
pub fn count_divisions_by_two(mut n: u64) -> u32 {
    if n <= 1 {
        return 0;
    }
    let mut steps = 0;
    while n > 1 {
        n /= 2;
        steps += 1;
    }
    steps
}

/// O(N) tiempo, O(1) espacio: Visita secuencial de cada elemento.
pub fn linear_sum(nums: &[i32]) -> i64 {
    let mut total: i64 = 0;
    for &num in nums {
        total += num as i64;
    }
    total
}

/// O(N^2) tiempo, O(N^2) espacio: Dos bucles anidados con reserva dinámica en el Heap.
pub fn find_all_pairs(nums: &[i32]) -> Vec<(i32, i32)> {
    let n = nums.len();
    let mut pairs = Vec::with_capacity(n * n);
    for i in 0..n {
        for j in 0..n {
            pairs.push((nums[i], nums[j]));
        }
    }
    pairs
}

/// O(N) tiempo, O(N) espacio en el Call Stack.
pub fn recursive_countdown_stack(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    1 + recursive_countdown_stack(n - 1)
}

/// O(N) tiempo, O(1) espacio: Mutación local sin marcos adicionales en el Stack.
pub fn iterative_countdown_memory(n: u64) -> u64 {
    let mut count = 0;
    for _ in 0..n {
        count += 1;
    }
    count
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_get_first_element() {
        let nums = [10, 20, 30];
        assert_eq!(get_first_element(&nums), Ok(10));
        let empty: [i32; 0] = [];
        assert_eq!(get_first_element(&empty), Err("Slice cannot be empty"));
    }

    #[test]
    fn test_count_divisions_by_two() {
        assert_eq!(count_divisions_by_two(1024), 10);
    }

    #[test]
    fn test_linear_sum() {
        assert_eq!(linear_sum(&[1, 2, 3, 4, 5]), 15);
    }

    #[test]
    fn test_find_all_pairs() {
        let nums = [1, 2];
        let pairs = find_all_pairs(&nums);
        assert_eq!(pairs, vec![(1, 1), (1, 2), (2, 1), (2, 2)]);
    }

    #[test]
    fn test_countdown_recursive_and_iterative() {
        assert_eq!(recursive_countdown_stack(5), 5);
        assert_eq!(iterative_countdown_memory(5), 5);
    }
}

Implementación Canónica en Python (practica/dia_02_big_o_examples.py)#

from typing import List, Tuple

def get_first_element(arr: List[int]) -> int:
    if not arr:
        raise ValueError("El arreglo no puede estar vacío.")
    return arr[0]

def count_divisions_by_two(n: int) -> int:
    if n <= 0:
        return 0
    steps = 0
    val = n
    while val > 1:
        val //= 2
        steps += 1
    return steps

def linear_sum(arr: List[int]) -> int:
    total = 0
    for num in arr:
        total += num
    return total

def find_all_pairs(arr: List[int]) -> List[Tuple[int, int]]:
    pairs = []
    for i in range(len(arr)):
        for j in range(len(arr)):
            pairs.append((arr[i], arr[j]))
    return pairs

5. Las 3 Trampas Clásicas en Entrevistas#

1. Confundir O(A + B) con O(A · B): - Cuando una función recibe dos listas distintas A y B, no puedes decir automáticamente O(N²) o O(N). - Si recorres la lista A y luego la lista B, es O(A + B). Si por cada elemento de A recorres toda la lista B, es O(A · B). Solo si A ≈ B = N, se simplifica a O(N²).
2. El Costo Oculto de Operaciones de Biblioteca: - vec.remove(0) o list.pop(0) parece una instrucción atómica simple, pero tiene costo O(N) porque obliga al sistema a desplazar en memoria todos los elementos posteriores. - En Python, x in lista es O(N) lineal, mientras que x in conjunto_hash es O(1) promedio.
3. Ignorar la Memoria de la Pila de Llamadas: - Muchos desarrolladores afirman que un algoritmo recursivo que no instancia arrays tiene espacio auxiliar O(1). Los entrevistadores buscan verificar si el candidato comprende el rol del Stack Frame.

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. Calcula el Big O temporal y espacial de tus soluciones previas: - Revisa tu código de LeetCode 704 (Binary Search): Demuestra por qué es O(log N) tiempo y O(1) espacio auxiliar.
2. LeetCode 1 — Two Sum (Easy): - Compara mentalmente la solución de fuerza bruta con dos bucles anidados (O(N²) tiempo, O(1) espacio) frente a la solución con Tabla Hash (O(N) tiempo, O(N) espacio). Este es el clásico intercambio o trade-off espacio-tiempo.
3. LeetCode 217 — Contains Duplicate (Easy): - Analiza las 3 alternativas canónicas:
4. Fuerza bruta: O(N²) tiempo, O(1) espacio.
5. Ordenamiento previo: O(N log N) tiempo, O(1) espacio in-place.
6. HashSet: O(N) tiempo, O(N) espacio.

Navegación:

• ← Volver a Sesión 01: Búsqueda Binaria
• Avanzar a Sesión 03: Arrays, Memoria y Strings en Rust y Python →