Trade-offs tiempo vs espacio

Casi todo algoritmo se puede acelerar gastando más memoria, y casi todo algoritmo se puede achicar en memoria pagando con tiempo. La pregunta no es "¿cuál es mejor?", es "¿qué importa más en este contexto?".

El ejemplo más simple: contar elementos duplicados

Solución O(n²) tiempo, O(1) espacio: dos loops anidados que comparan cada par.

def hay_duplicado(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

Solución O(n) tiempo, O(n) espacio: hash set.

def hay_duplicado(arr):
    vistos = set()
    for x in arr:
        if x in vistos:
            return True
        vistos.add(x)
    return False

Gastamos un set de tamaño n para evitar el segundo loop. Cuando arr tiene un millón de elementos, la primera versión tarda años; la segunda termina en un segundo.

Memoización: el caso más visible

Fibonacci recursivo ingenuo es O(2^n) tiempo, O(n) espacio (la pila). Memoizando, es O(n) tiempo, O(n) espacio.

Gastamos un diccionario de n entradas para evitar recalcular subproblemas. Buen intercambio: bajamos exponencial a lineal.

DP iterativo (tabulación) suele ser O(n) tiempo, O(n) espacio. Algunos problemas permiten reducir el espacio a O(1) si solo necesitas los últimos valores. Por ejemplo, fibonacci iterativo solo guarda los dos anteriores.

Espacio para ganar tiempo (los más comunes)

• Hash set / hash map: convierten búsqueda O(n) en O(1). Coste: O(n) espacio.
• Memoización: convierten recursión exponencial en polinomial. Coste: O(n) espacio.
• Tabla precalculada: si vas a consultar f(x) muchas veces, calcula todos los valores una vez y leelos en O(1). Coste: O(rango) espacio.
• Prefix sums: calculas una vez en O(n), después cualquier rango se consulta en O(1). Coste: O(n) espacio.

Tiempo para ganar espacio (los menos comunes pero importantes)

• In-place algorithms: ordenamientos como heap sort y quick sort modifican el arreglo original. Coste: el algoritmo es más complejo y a veces más lento por constante, pero O(1) espacio extra.
• Stream processing: si no puedes cargar todos los datos en memoria, procesás de a poco. Coste: a veces más pasadas sobre los datos.
• Bit packing: guardar N booleanos en N/8 bytes en lugar de N enteros. Coste: operaciones de bit en cada lectura/escritura.

Cuándo cada uno importa

Cuándo gastar memoria sin preocuparte:

• Tu input es chico (< 10^6 elementos) y tienes RAM de sobra.
• El problema es claramente CPU-bound y la memoria no es escasa.
• Entrevistas: casi siempre, el entrevistador valora más una solución O(n) tiempo + O(n) espacio que una O(n²) tiempo + O(1) espacio.

Cuándo cuidar la memoria:

• Tu input es masivo (cientos de millones, miles de millones de elementos).
• Sistemas embebidos con RAM limitada.
• Procesos que corren en paralelo y comparten memoria.
• Tu lenguaje tiene garbage collector que pausa el programa: cuanta más memoria, más pausas.

Ejemplo concreto: encontrar el elemento mayoritario

Problema: encontrar el elemento que aparece más de N/2 veces en un arreglo (si existe).

Solución con hash map (O(n) tiempo, O(n) espacio):

def mayoritario(arr):
    cuenta = {}
    for x in arr:
        cuenta[x] = cuenta.get(x, 0) + 1
    for x, c in cuenta.items():
        if c > len(arr) // 2:
            return x
    return None

Solución Boyer-Moore voting (O(n) tiempo, O(1) espacio):

def mayoritario(arr):
    candidato, cuenta = None, 0
    for x in arr:
        if cuenta == 0:
            candidato = x
        cuenta += 1 if x == candidato else -1
    return candidato

Misma complejidad de tiempo, mucho menos memoria. Pero el código es menos obvio. En una entrevista, presentaría la primera primero y mencionaría la segunda como mejora si me lo piden.

Cómo presentar trade-offs en una entrevista

Cuando termines una solución, mencioná la complejidad y proponé el trade-off:

"Esto es O(n²) tiempo, O(1) espacio. Si gastamos O(n) espacio en un hash set, bajamos a O(n) tiempo. ¿Qué priorizamos?"

Eso muestra que pensaste el problema, no que copiaste la primera solución que te vino. La mayoría de los entrevistadores van a decir "vamos por la rápida". Algunos te van a desafiar a hacer O(n) tiempo Y O(1) espacio (a veces es posible, a veces no).

La regla final

No hay respuesta universal. La pregunta correcta no es "¿es bueno gastar memoria?". Es:

1. ¿Cuánto input voy a procesar?
2. ¿Cuánta memoria tengo disponible?
3. ¿Qué tan crítico es el tiempo de respuesta?
4. ¿Cuánta complejidad de código estoy dispuesto a aceptar?

Con esas cuatro preguntas, casi cualquier trade-off se decide solo.