Qué es la complejidad espacial

Las casillas que usa un algoritmo además de la respuesta

Supongamos que queremos el mayor de seis números. Al final, la respuesta es un solo número, pero el camino cambia según la solución. Una apunta en una sola nota el mayor visto hasta ahora y lo reescribe en el mismo sitio cada vez que aparece uno más grande, así que la nota sigue siendo una. Si en cambio anota cada nuevo mayor en una casilla nueva, las casillas aumentan a medida que avanza, y si copia todos los números para ordenarlos de mayor a menor, necesita tantas casillas extra como la entrada. Esas casillas temporales que se usan mientras se fabrica la respuesta son el costo en espacio. La entrada nos la dieron de todos modos, así que no cuenta; solo contamos las casillas que el algoritmo despliega encima.

La entrada (dorado) nos la dieron, así que no es un costo. Al encender las casillas temporales aparece el registro (azul) que guarda esta solución al anotar cada nuevo mayor en una casilla nueva. Solo esas casillas extra cuentan como costo.

Al medir el espacio dejamos fuera la entrada y miramos solo las casillas extra, porque así la comparación es justa: si dos soluciones reciben la misma entrada, hay que contar solo lo que cada una usa de más. Entonces, ¿la solución que se arregla con una nota es siempre la mejor? Si ahorramos espacio, ¿no perderemos en otra parte? Lo siguiente es el trato entre tiempo y espacio.

Más espacio, más rapidez; menos espacio, más lentitud (el intercambio)

Incluso para el mismo problema, la velocidad depende de cómo se use el espacio. Supongamos que hay que consultar un valor a menudo. Una forma es calcular de antemano todas las respuestas y escribirlas en una tabla. Cada consulta es un vistazo a la tabla, así que es muy rápida, pero hay que reservar espacio para guardarla. Otra forma es no hacer tabla y volver a calcular desde cero en cada consulta. Casi no ocupa espacio, pero es lenta porque repite el mismo trabajo cada vez. Ceder espacio para ganar tiempo, o ceder tiempo para ahorrar espacio: eso es el intercambio entre tiempo y espacio.

Alterna entre gastar más espacio y ahorrar espacio. El lado con una tabla preparada (azul) usa mucho espacio pero es rápido; el que cuenta cada vez sin tabla (dorado) ahorra espacio pero es lento. Mismo problema, distinto trato.

Ningún lado tiene siempre razón; se elige según la situación. Si vas a consultar a menudo, conviene hacer la tabla y ceder espacio; si el espacio es escaso, es mejor resolver sin tabla aunque tarde un poco más. Pero ¿qué significa en concreto ahorrar espacio? En una tarea tan común como ordenar, pongamos lado a lado una solución que no usa ninguna casilla extra y otra que usa una copia entera del tamaño de la entrada.

Ordenar en el sitio vs hacer una copia

Supongamos que queremos poner en fila unos números desordenados, de menor a mayor. Una forma es ordenarlos intercambiando de dos en dos sus posiciones dentro de las casillas que recibimos. No creamos ni una casilla nueva; solo cambiamos posiciones dentro de las que tenemos. Esto se llama ordenar en el sitio, y el espacio extra es cero. Otra forma es preparar tantas casillas vacías como elementos tenga la entrada, y luego ir eligiendo el menor y pasándolo a esas casillas nuevas. El resultado es la misma fila ordenada, pero usamos un juego entero de casillas extra del tamaño de la entrada. Las dos soluciones dan la respuesta correcta, pero el costo en espacio cambia mucho: cero, o tanto como la entrada.

Elige ordenar en el sitio o hacer una copia y ejecuta el orden. En el sitio (dorado) solo intercambia posiciones en las mismas casillas, así que el extra es 0; la copia (azul) crea casillas nuevas del tamaño de la entrada. Mismo resultado, distinto costo en espacio.

En el sitio, cero extra; la copia, tanto como la entrada. La respuesta es la misma, pero el costo en espacio se separó con claridad. ¿No suena conocido eso de «cero o tanto como la entrada»? Al medir el tiempo en la lección anterior también distinguimos el trabajo que no crece con la entrada del que crece con ella. Esa misma lente se puede aplicar tal cual al espacio. A continuación haremos crecer la entrada para ver cómo crece el espacio extra.

El espacio también crece con la entrada (O(1) u O(n))

En la lección anterior, la O grande resumía en un símbolo cómo crece el tiempo cuando crece la entrada. Usamos el mismo resumen para el espacio. La solución que busca el mayor con una sola nota siempre tiene una casilla extra, sean seis números o cien. Por mucho que crezca la entrada, el espacio extra no cambia, así que lo llamamos espacio O(1). En cambio, la solución que hace una copia duplica sus casillas nuevas cuando la entrada se duplica. Su espacio extra crece en proporción directa a la entrada, así que es espacio O(n). Con la misma herramienta, la O grande, ahora medimos la forma en que crece el espacio y no el tiempo.

Haz crecer la entrada para aumentar n. O(1) (dorado) mantiene una sola casilla extra por grande que sea la entrada; O(n) (azul) crece junto con ella. Es la O grande aplicada directamente al espacio.

Es la misma notación O grande, pero esta vez pegada al espacio y no al tiempo. O(1) significa que el espacio extra se queda en una constante pequeña por grande que sea la entrada; O(n), que crece a la par de la entrada. Así podemos mirar un algoritmo con dos ojos: cuánto tiempo tarda y cuánto espacio usa. Ahora hay que juntar las dos cosas en una línea.

Resumen: un segundo ojo para mirar algoritmos

En una línea, sería así. Mientras produce la respuesta, un algoritmo usa casillas temporales además de la respuesta, y esas casillas extra son su costo en espacio; la entrada no se cuenta. El espacio y el tiempo se intercambian a menudo: si preparas una tabla y usas más espacio, va más rápido; si resuelves en el sitio y ahorras espacio, va más lento. El espacio extra también crece con la entrada: siempre una casilla es O(1), tanto como la entrada es O(n). Por eso, al elegir un buen algoritmo, no basta con mirar la velocidad. Solo al ver juntas cuánta rapidez tiene y cuánto espacio usa se puede elegir bien. En un aparato pequeño con poca memoria, la solución lenta que ahorra espacio suele ser la correcta.

Toca los cuatro pasos en orden para enlazarlos en una línea: las casillas extra además de la respuesta, el intercambio espacio↔tiempo, en el sitio vs una copia y el espacio que crece con la entrada (O(1)/O(n)). La complejidad espacial cabe en un solo panel.

Ahora podemos medir un algoritmo con dos varas a la vez: tiempo y espacio. Entre varias soluciones que dan la misma respuesta, tenemos criterio para decidir cuál elegir en cada situación. Poner en la balanza no solo la velocidad, sino también el costo en espacio, es lo que significa elegir bien un algoritmo. En la próxima lección, con las dos varas en la mano, daremos un paso más hacia formas más ingeniosas de resolver problemas reales.