Cómo NEGOCIAR TIEMPO vs ESPACIO

Puedes ser un buen programador sin ir a la universidad, pero no puedes ser un buen programador intermedio sin conocer la teoría de la complejidad computacional básica. No necesitas conocer la notación de la "gran O'', pero personalmente pienso que
deberías ser capaz de comprender la diferencia entre "constantes de tiempo'', "n logaritmo de n'' y "n al cuadrado''. Podrías ser capaz de intuir cómo negociar tiempo frente a espacio sin ese conocimiento, pero en su ausencia no tendrás una base firme
para comunicarte con tus colegas.

Al diseñar o comprender de un algoritmo, la cantidad de tiempo que toma para ejecutarse es a veces una función del tamaño de la entrada. Cuando eso es cierto, podemos decir que el peor, el mejor y el caso esperado de tiempo de ejecución de un algoritmo es "n log n'' si es proporcional al tamaño ($n$) veces el logaritmo del tamaño. La notación y forma de hablar puede ser también aplicada al espacio tomado por una estructura de datos.

Para mí, la teoría de la complejidad computacional es bella y tan profunda como la física---¡y con poquito margen continúan juntas por un largo trecho! El tiempo (los ciclos del procesador) y el espacio (la memoria) pueden ser negociados entre sí. La ingeniería trata acerca de compromisos, y este es un buen ejemplo. No siempre es sistemática. En general, sin embargo, uno puede ahorrar espacio al codificar las cosas más fuertemente, al costo de más tiempo de computación cuando tienes que decodificarlas. Puedes ahorrar tiempo mediante el cacheo, o sea, al invertir espacio para almacenar una copia local de algo, al costo de tener que mantener la consistencia del caché. Puedes a veces ahorrar tiempo manteniendo más información en una estructura de datos. Esto usualmente cuesta una pequeña cantidad de espacio pero puede complicar el algoritmo.

Mejorar el intercambio espacio/tiempo puede a menudo cambiar a uno o al otro dramáticamente. Sin embargo, antes de que trabajes en esto deberías preguntarte a ti mismo si lo que estás mejorando es realmente lo que necesita la mejoría. Es divertido trabajar en un algoritmo, pero no puedes permitir que te ciegue hasta el frío y duro hecho de que el mejorar algo que no es un problema no hará ninguna notable diferencia y que sólo creará una carga de prueba.

La memoria en las modernas computadoras parece barata, debido a que a diferencia del tiempo de procesador, no puedes verla en uso hasta que golpeas la pared; pero entonces la falla es catastrófica. Hay también otros costos ocultos al usar la memoria,
tales como su efecto en otros programas que deben ser residentes, y el tiempo para asignarla y desasignarla. Considera esto cuidadosamente antes de que sacrifiques espacio para ganar velocidad.