¿Cómo intercambias complejidad temporal por espacial?

Respuesta directa

Qué debe cubrir una buena respuesta

Cómo funciona

La decisión trata de qué recurso es más escaso para este problema a esta escala. Gastar memoria compra velocidad cuando una tabla de búsqueda, un índice hash, una suma de prefijos precalculada o una caché de memoización sustituyen trabajo repetido, convirtiendo un recorrido cuadrático en tiempo lineal. Gastar tiempo compra memoria cuando la entrada no cabe, cuando basta una pasada en streaming o cuando la propia asignación es el cuello de botella. La decisión necesita números reales: tamaño de entrada, techo de memoria, si la operación corre una vez o un millón, y el coste de un fallo de caché.

Ejemplo

Encontrar pares que suman un objetivo en un array de un millón de enteros tarda minutos con un bucle anidado y milisegundos con un conjunto hash de valores vistos que usa unos pocos megabytes. En sentido contrario: deduplicar un log de 200 GB en una máquina con 8 GB de RAM no puede mantener un conjunto de todo, así que ordena externamente por trozos y fusiona, cambiando pasadas extra por memoria acotada.

Errores frecuentes

• Citar Big-O sin decir el tamaño de entrada que hace que la diferencia importe.
• Añadir una caché que crece sin límite y convierte un problema de velocidad en una caída.
• Optimizar una función que corre una vez al arrancar mientras el bucle caliente sigue igual.

Una estructura útil para responder

Responde desde tu propia experiencia.

No memorices un guion: usa solo ejemplos que puedas explicar con honestidad en preguntas posteriores.