Complejidad espacial: el espacio también cuesta
La lección pasada medimos la velocidad de un algoritmo no en segundos sino por cuánto crece su trabajo a medida que crece la entrada. Pero persiguiendo solo la velocidad, es fácil pasar por alto una cosa. Mientras un algoritmo trabaja, garabatea en papel borrador, despliega casillas de sobra, arma tablas, todo aparte de la respuesta misma. Dicho de otro modo, no solo gasta tiempo; también gasta espacio. ¿Ese espacio es gratis? Para la mismísima respuesta, una solución usa una sola casilla extra en el escritorio mientras otra extiende toda una segunda hoja. ¿Cómo medimos esa diferencia, y por qué debería importarnos?
Las casillas que un algoritmo usa más allá de la respuesta
Digamos que queremos el mayor de seis números. La respuesta es, al final, un solo número. Pero mientras lo hallamos, una solución guarda el mayor visto hasta ahora en una pequeña nota y lo reescribe cada vez que aparece un número más grande. La nota sigue siendo una hoja. Otra solución copia todos los números una vez más para acomodarlos de mayor a menor. Estas casillas de borrador, anotadas no como la respuesta misma sino en el proceso de hacerla, son exactamente el costo del espacio. La entrada igual nos la dieron, así que no cuenta como costo; contamos solo las casillas que el algoritmo despliega encima.
La entrada (dorado) solo nos la entregaron. Toca encender casillas temporales para ver las casillas (azul) que el algoritmo despliega más allá de la respuesta. Solo estas casillas extra cuentan como costo.
La clave es que, al medir el espacio, dejamos fuera la entrada y miramos solo las casillas extra. Eso es lo que nos deja comparar con justicia dos soluciones con la misma entrada. Pero piénsalo. ¿La solución que se arregla con una sola nota es siempre la mejor? Al ahorrar espacio, ¿no perderemos en otro lado? A continuación, miremos el trato entre el tiempo y el espacio.
Más espacio, más rápido; menos espacio, más lento (el canje)
Para el mismo problema, la velocidad cambia según cómo uses el espacio. Digamos que tienes que consultar cierto valor a menudo. Una forma es calcular todas las respuestas por adelantado y escribirlas en una tabla. Cada consulta es solo un vistazo a la tabla, así que es muy rápido. A cambio, debes apartar espacio para guardar esa tabla. Otra forma es saltarte la tabla y recalcular desde cero en cada consulta. Casi no cuesta espacio, pero es lento porque rehace el mismo trabajo cada vez. Ceder espacio para comprar tiempo, o ceder tiempo para ahorrar espacio. Esto es el canje entre tiempo y espacio.
Toca gastar más espacio y ahorrar espacio. El lado con tabla ya hecha (azul) usa mucho espacio y es rápido; el que cuenta cada vez (dorado) ahorra espacio y es lento. Mismo problema, distinto trato.
Vimos que ningún lado es simplemente correcto; eliges según la situación. Si vas a preguntar a menudo, armar una tabla y gastar espacio rinde; si el espacio escasea, resolver sin tabla es mejor aunque sea un poco lento. Pero ¿qué significa ahorrar espacio en concreto? En una tarea común como ordenar, pongamos lado a lado una solución que usa cero casillas extra y otra que usa toda una copia extra del tamaño de la entrada.
Resolver en el lugar frente a hacer una copia
Digamos que ordenamos números dispersos de menor a mayor. Una forma es acomodarlos intercambiando las posiciones de dos números dentro de las casillas que nos dieron. No hacemos ni una casilla nueva; solo cambiamos posiciones dentro de las que tenemos. Esto se llama ordenar en el lugar, y el espacio extra es cero. Otra forma es preparar tantas casillas vacías como tenga la entrada, luego elegir la menor cada vez y moverla a esas casillas nuevas. El resultado es la misma fila ordenada, pero usamos todo un juego extra de casillas, del tamaño de la entrada. El espacio extra cuesta tanto como la entrada. Ambas soluciones dan la respuesta correcta, pero el costo del espacio difiere mucho: cero, o el tamaño de la entrada.
Elige ordenar en el lugar o hacer una copia, luego toca ejecutar el orden. En el lugar (dorado) solo intercambia dentro de las mismas casillas, extra 0; la copia (azul) hace casillas nuevas del tamaño de la entrada. Mismo resultado, distinto costo de espacio.
En el lugar, cero extra; una copia, el tamaño de la entrada. Misma respuesta, y aun así el costo del espacio claramente se separó. Pero esta forma de decirlo, cero frente al tamaño de la entrada, ¿no suena familiar? La lección pasada, midiendo el tiempo, hablamos de qué pasa cuando el trabajo no crece a medida que crece la entrada, y cuando crece con ella. Esa misma lente la podemos poner sobre el espacio. A continuación, agrandemos la entrada y veamos cómo crece el espacio extra.
El espacio también crece con la entrada (O(1) u O(n))
El big-O de la lección pasada resumía, en un solo símbolo, cómo crece el tiempo a medida que crece la entrada. Usamos ese mismísimo resumen para el espacio. La solución que halla el mayor en una nota tiene una casilla extra que se queda en una, ya sea la entrada de seis o de cien. Por grande que sea la entrada, el espacio extra no se mueve, así que a esto lo llamamos espacio O(1). La solución que hace una copia, en cambio, duplica sus casillas nuevas cuando la entrada se duplica. El espacio extra crece en proporción directa a la entrada, así que esto es espacio O(n). El punto es que con big-O, la misma herramienta, ahora medimos la forma en que crece el espacio, no el tiempo.
Toca agrandar la entrada para subir n. O(1) (dorado) mantiene una sola casilla extra por grande que sea la entrada; O(n) (azul) crece junto con ella. Esto es big-O aplicado directo al espacio.
La misma notación big-O, pero esta vez pegada al espacio, no al tiempo. O(1) significa que el espacio extra queda fijado a una constante pequeña por grande que sea la entrada; O(n) significa que crece justo junto con la entrada. Así que ahora vemos un algoritmo con dos ojos: cuánto tiempo toma, y cuánto espacio usa. Juntemos estos dos en una sola línea.
En resumen: un segundo ojo para mirar los algoritmos
Visto en una línea, va así. Mientras produce la respuesta, un algoritmo usa casillas temporales más allá de la respuesta. Esas casillas extra son el costo del espacio, y la entrada se deja fuera del costo. El espacio y el tiempo a menudo se canjean: arma una tabla por adelantado y gasta más espacio para ir más rápido, o resuelve en el lugar y ahorra espacio y ve más lento. Y el espacio extra también crece con la entrada: siempre una casilla es O(1), tanto como la entrada es O(n). Así que al elegir un buen algoritmo, no puedes mirar solo la velocidad. Cuán rápido es y cuánto espacio usa, vistos juntos con dos ojos, es lo que por fin te deja elegir bien. En un aparato pequeño donde la memoria escasea, la solución lenta pero que ahorra espacio suele ser la respuesta correcta.
Toca los cuatro pasos en orden para hilarlos en una línea. Las casillas extra más allá de la respuesta, el canje espacio-tiempo, en el lugar frente a una copia, y el espacio que crece con la entrada (O(1) u O(n)). La complejidad espacial en un panel.
Ahora podemos medir un algoritmo con dos varas a la vez, tiempo y espacio. Entre varias soluciones que dan la misma respuesta, ganamos un ojo para juzgar cuál elegir en cada situación. Poner en la balanza no solo la velocidad sino el costo del espacio es lo que por fin equivale a elegir un algoritmo como un adulto. En la próxima lección, llevando ambas varas, damos un paso más hacia formas más astutas de resolver problemas reales.