Complejidad espacial: Cómo utilizan la memoria los algoritmos

La complejidad espacial mide el uso de memoria de los algoritmos a medida que aumenta el tamaño de la entrada. Esto hace que comprender la complejidad espacial sea importante para la gestión de recursos en entornos con limitaciones.

En este artículo, explicaré en detalle qué es la complejidad espacial, cómo calcularla y cómo minimizarla. Además, trataré aplicaciones del mundo real y ofreceré fundamentos teóricos.

Comprender la complejidad espacial

Antes de sumergirnos en cálculos y optimizaciones, aclaremos qué significa realmente la complejidad espacial y por qué debería importarte.

¿Qué es la complejidad espacial?

La complejidad espacial es la memoria total que requiere el algoritmo en relación con el tamaño de la entrada. Es relevante para analizar la huella de memoria en el peor de los casos para la escalabilidad del sistema, y el espacio total incluye la entrada, el espacio auxiliar y la sobrecarga, mientras que el espacio auxiliar es la memoria adicional que excluye la entrada y la salida. Tomemos, por ejemplo, la clasificación de un arreglo: El espacio total incluye el arreglo en sí, mientras que el espacio auxiliar podría ser el espacio temporal en la clasificación por fusión.

Por qué es importante la complejidad espacial

En la informática moderna, la eficiencia del espacio suele ser fundamental. Al optimizar la complejidad del espacio, te aseguras de que tus algoritmos se ejecuten en dispositivos con RAM limitada, como sistemas integrados en IoT o teléfonos inteligentes, o incluso en grandes sistemas con procedimientos que requieren muchos recursos, en los que cada bit de RAM es importante.

Pensemos, por ejemplo, en las aplicaciones móviles: optimizar la complejidad del espacio ayuda a evitar fallos durante el procesamiento de imágenes. O piensa en el ahorro de costes que supone el cloud computing en cuanto a almacenamiento o transmisión de datos, y en la posibilidad de obtener análisis en tiempo real sin necesidad de cargar todos los datos.

Análisis asintótico y notación Big O para el espacio

En esta sección, explicaré cómo las notaciones asintóticas como Big O describen el crecimiento del espacio y te proporcionaré herramientas para limitar y comparar el uso de la memoria.

Introducción a la notación Big O

Matemáticamente, una función f(n) está dominada por una función g(n) si existe una constante c y k, tal que para todo k>n, 0 ≤ |f(n)| ≤ |g(n)|.

En este caso, escribimos f(n)=O(g(n)), y decimos que f(n) es O grande de g(n).

En términos más sencillos, esto significa que f(n) no crece más rápido que g(n) a partir de un determinado índice.

La notación Big O representa el límite superior del espacio como una función del tamaño de entrada n, de modo que podemos centrarnos en los términos dominantes para n grande.  Esta notación ayuda a clasificar algoritmos; por ejemplo, O(n) significa que el espacio se duplica al duplicarse la entrada.

Existe un malentendido común entre los principiantes de que Big O para el espacio ignora constantes como 2n es O(n), pero en la práctica, las constantes son importantes para n pequeño.

Notaciones asintóticas relacionadas

Hay diferentes maneras de modelar la complejidad y diferentes notaciones. Por ejemplo, Big Omega proporciona un límite inferior que resulta útil para demostrar necesidades mínimas de espacio, como por ejemplo que la clasificación requiere al menos Ω(n). Otra notación es la Big Theta, que proporciona un límite ajustado cuando el superior y el inferior coinciden, lo que la hace ideal para análisis precisos, como O(n) = Θ(n) para el espacio lineal.

Otras convenciones notacionales

Existen otras convenciones notacionales relevantes para la literatura sobre complejidad espacial, como la notación Soft-O Õ, que ignora los factores polilógicos. Es habitual en algoritmos avanzados como el procesamiento de grafos, donde los registros son insignificantes. Aparece en artículos teóricos sobre complejidades aproximadas como Õ para el espacio sublineal en algoritmos de streaming.

Componentes de la complejidad espacial

La complejidad espacial tiene muchos factores que contribuyen a ella y muchos puntos de optimización en el diseño de algoritmos. Veamos:

Requisitos de espacio de entrada

Los datos de entrada ocupan un espacio proporcional al tamaño, como por ejemplo O(n) para un arreglo o para analizar un gran conjunto de datos como secuencias genómicas.

En las entrevistas de programación del mundo real, es habitual excluir el espacio de entrada al calcular el espacio auxiliar y centrarse únicamente en la memoria adicional que utiliza el algoritmo. Sin embargo, en la programación competitiva, el espacio total suele incluir la entrada.

Espacio auxiliar y memoria temporal

El espacio auxiliar es la memoria adicional que necesita un algoritmo para realizar sus operaciones. Afecta directamente al diseño del algoritmo.

Por lo tanto, puedes, por ejemplo, utilizar O(n) para el arreglo temporal en un algoritmo de ordenación por fusión. Otro ejemplo serían las tablas hash para duplicados (O(n)), las pilas de recursión para la coincidencia de paréntesis (O(n)) y muchos otros.

Algunos ejemplos clásicos de espacio auxiliar son los métodos de dos punteros (O(1)), los algoritmos de ventana deslizante que utilizan una cola doble (O(k)) y el BFS, que requiere un espacio O(V) para tu conjunto visitado y tu cola.

El siguiente código muestra un ejemplo de una operación de ordenación por fusión en el arreglo temporal durante la etapa de fusión:

def merge(left_half, right_half):
    merged = [0] * (len(left_half) + len(right_half))  # O(n) auxiliary space
    left_idx = right_idx = merged_idx = 0
    # merging logic...

La pila de llamadas y el espacio de recursividad

Cada llamada recursiva añade un marco de pila (dirección de retorno + parámetros + variables locales).

Por otro lado, la recursión lineal, como el factorial o el DFS en una lista enlazada, tiene una pila O(n).

La recursividad binaria, al igual que la recursividad ingenua de Fibonacci o la recursividad de árbol, tiene un O(n) en el peor de los casos.

La optimización de llamadas de cola, que es compatible con Scheme, Rust y, en ocasiones, Python con decoradores, se reduce a O(1). Sin embargo, el verdadero peligro aquí radica en el límite de recursividad predeterminado de Python, que es de alrededor de 1000, lo que provocaría un desbordamiento de la pila en árboles profundos.

Aquí tienes un ejemplo de Fibonacci recursivo ingenuo que muestra el crecimiento de la pila:

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # O(n) stack depth

Echa un vistazo a nuestro blog sobre el análisis de la complejidad del código mediante Python para obtener más información sobre el análisis de complejidad de Python.

Sobrecarga de la estructura de datos

Lo bueno de la sobrecarga de la estructura de datos es su simplicidad, ya que todas las estructuras añaden costes fijos o por elemento, como la sobrecarga mínima de un arreglo, el doble espacio de los punteros de las listas enlazadas y muchos otros ejemplos. 

En cualquier caso, el lenguaje de programación tiene una influencia enorme. Las listas de Python tienen una sobrecarga dinámica, a diferencia de los arreglos de C; por ejemplo, los mapas hash con un factor de carga del 75 % desperdician espacio en los corchetes vacíos.

Tipos de complejidad espacial

Complejidad espacial constante: O(1)

La complejidad espacial constante es la solución fundamental y óptima, si se encuentra. Muchos algoritmos conocidos tienen una complejidad verdaderamente constante, como los simples intercambios de variables del ejemplo siguiente, que es un simple intercambio in situ utilizando el desempaquetado de tuplas de Python:

def swap_numbers(first, second):
    first, second = second, first  # O(1) — only two variables
    return first, second

Otros algoritmos conocidos de complejidad constante son la partición de la bandera holandesa en el ordenamiento rápido y el recorrido de Morris para árboles. Sin embargo, existe un límite práctico en el que puedes tener unas pocas docenas de variables antes de que resulte efectivo, ya que, dependiendo del hardware del sistema, en el peor de los casos, O(1) a veces puede no ser suficiente si la memoria necesaria supera los recursos del sistema.

Complejidad del espacio lineal: O(n)

La complejidad espacial lineal se define simplemente como proporcional a la entrada. Un par de ejemplos serían un arreglo adicional para copiar o un conjunto hash para elementos únicos. El caso de uso más común se da en los patrones de procesamiento de datos, como el filtrado de listas.

Complejidad espacial logarítmica y sublineal

Una complejidad espacial logarítmica significa que la cantidad de memoria que utiliza un algoritmo crece muy lentamente a medida que aumenta el tamaño de la entrada. Concretamente, es proporcional al logaritmo del tamaño de la entrada.

Por ejemplo, una recursividad de búsqueda binaria tiene una profundidad de pila O(log(n)), al igual que el método de divide y vencerás con recursividad de cola o los algoritmos de streaming, que aproximan los resultados en un espacio O(log(n)) u O(sqrt(n)).

Las complejidades logarítmicas y sublineales son poco frecuentes, pero resultan muy potentes para conjuntos de datos masivos. Puedes ver un ejemplo de complejidad logarítmica con la búsqueda binaria iterativa (espacio constante) como muestra el código de ejemplo a continuación:

def binary_search(numbers, target):
    left = 0
    right = len(numbers) - 1
    while left <= right:                 # O(1) space total
        mid = (left + right) // 2
        # comparison logic...

Complejidad espacial cuadrática: O(n²)

Se produce una complejidad espacial cuadrática cuando los requisitos de memoria aumentan con el cuadrado de la entrada. Un ejemplo común sería la tabla de programación dinámica 2D, que tiene una complejidad de O(n²) o una matriz de adyacencia para grafos con complejidad O(V²). Sin embargo, es importante señalar que esta complejidad se vuelve poco práctica cuando se superan los miles de elementos de entrada.

Complejidad espacial exponencial y factorial

La complejidad exponencial, como su nombre indica, hace que el crecimiento de la memoria necesaria sea proporcional al tamaño de la entrada elevado a O(2^n), y esto ocurre, por ejemplo, cuando se almacenan todos los subconjuntos o las rutas de los árboles de decisión.

Del mismo modo, en la complejidad factorial, la memoria necesaria es proporcional al factorial del tamaño de la entrada O(n!), y esto ocurre cuando enumeras todas las permutaciones de la entrada. Sin embargo, estas complejidades suelen ser muy costosas y, con toda seguridad, inviables para n>20-30 en la mayoría de los sistemas. Si estás trabajando con esto, es posible que realmente necesites recortar, aproximar o adoptar un enfoque diferente.

Cómo calcular la complejidad espacial

El análisis sistemático identifica todas las asignaciones de memoria y sus patrones de crecimiento:

Enfoque de análisis línea por línea

El primer paso es examinar tu código línea por línea e identificar cada variable, arreglo y asignación de objetos. El siguiente paso es determinar si el tamaño de cada asignación depende de los parámetros de entrada. A continuación, suma la memoria para las asignaciones independientes y toma el máximo para las ramas mutuamente excluyentes. Por último, se programa la asignación de pila para las variables locales y la asignación de montón para la memoria dinámica. Aquí tienes un ejemplo:

def linear_search(arr, target):
    n = len(arr)           # O(1) - single integer
    for i in range(n):     # O(1) - loop variable
        if arr[i] == target:
            return i
    return -1
# Total: O(1) auxiliary space

Análisis de complejidad recursiva

La complejidad espacial de la recursividad es igual a la profundidad máxima de recursividad multiplicada por el espacio por marco de llamada, a lo que hay que añadir cualquier estructura de datos auxiliar asignada durante la recursividad, identificar el caso base y analizar cómo se relaciona la profundidad de recursividad con el tamaño de la entrada. Por ejemplo, la secuencia de Fibonacci ingenua crea una profundidad O(n) con O(1) por marco, lo que da un total de espacio de pila O(n). Aquí tienes un ejemplo de cálculo del espacio factorial:

def factorial(n):
    if n <= 1:             # Base case
        return 1
    return n * factorial(n - 1)
# Space: O(n)

Análisis de la complejidad de la programación dinámica

Las tablas DP estándar tienen dimensiones que coinciden con los parámetros del subproblema; por lo tanto, un problema unidimensional requiere un espacio O(n), y los problemas bidimensionales necesitan O(nxm). Las técnicas de optimización, como los arreglos rodantes, reducen una dimensión para transformar, por ejemplo, O(n²) en O(n). La compresión de estado aprovecha las dependencias, por lo que si la fila i solo necesita i-1, basta con almacenar dos filas. Aquí tienes un ejemplo de Fibonacci optimizado para el espacio utilizando solo dos variables:

def fibonacci_optimized(n):
    previous = 0
    current = 1
    for _ in range(2, n + 1):            # O(1) space
        previous, current = current, previous + current
    return current

Si tienes curiosidad por saber más sobre la dimensionalidad y su reducción, te recomiendo que consultes nuestros tutoriales sobre Dominar las dimensiones de cambio lento (SCD) y « » (Comprender la cardinalidad: Retos y soluciones para flujos de trabajo con gran volumen de datos.

Pasos para calcular la complejidad espacial en la práctica

Para calcular la complejidad espacial en la práctica, sigue estos pasos:

1. Aclara si el espacio de entrada está incluido en función del contexto.
2. Contar variables y constantes de tamaño fijo. Contribuyen con O(1)
3. Mide las estructuras auxiliares, como arreglos y mapas hash, en relación con el tamaño de la entrada.
4. Calcular la profundidad máxima de recursividad para la contribución al espacio de la pila.
5. Combina todos los componentes y exprésalos utilizando el límite asintótico más estricto.

La complejidad espacial de los algoritmos comunes

Requisitos de espacio del algoritmo de clasificación

El algoritmo de ordenación por mezcla requiere un espacio auxiliar O(n) para los arreglos temporales durante la mezcla. Por otro lado, Quicksort utiliza solo un espacio de pila promedio de O(log n), pero O(n) en el peor de los casos sin optimización. Mientras que el ordenamiento por montón solo alcanza un espacio auxiliar O(1) al ordenar in situ, como muestra el siguiente código:

def heapify(array, heap_size, root_index):
    largest = root_index
    left_child = 2 * root_index + 1
    right_child = 2 * root_index + 2
    # comparison & swap logic...       # O(1) auxiliary space

Por último, el ordenamiento por recuento necesita un espacio O(k), donde k es el rango de valores, pero no resulta práctico cuando k>>n.

Complejidad espacial de los algoritmos gráficos

El recorrido de grafos tiene muchos algoritmos. Por ejemplo, la búsqueda en anchura (BFS) mantiene una cola que requiere un espacio O(V) para los vértices, mientras que la búsqueda en profundidad (DFS) utiliza un espacio de pila O(V) en el peor de los casos para la profundidad máxima.  El algoritmo de Dijkstra, por otro lado, necesita O(V) para la cola de prioridades y el seguimiento de la distancia para cada uno. La representación gráfica es importante porque la matriz de adyacencia utiliza O(V²), mientras que la lista de adyacencia utiliza O(V+E). 

Características del espacio de la estructura de datos

Existen diferentes estructuras de datos y cada una requiere diferentes asignaciones de memoria. Por ejemplo, los arreglos y las listas de arreglos almacenan n elementos en memoria contigua O(n), las listas enlazadas requieren espacio O(n) más la sobrecarga del puntero para cada nodo, los árboles binarios utilizan espacio O(n) con 2-3 punteros por nodo, lo que añade una sobrecarga significativa, las tablas hash consumen espacio O(n) multiplicado por el factor de carga, que suele variar entre 1,5 y 3 veces, y las listas de adyacencia proporcionan una eficiencia de espacio O(V+E) para grafos dispersos.

Ejemplos de cálculos de complejidad espacial

A continuación se muestran ejemplos para el cálculo de la complejidad espacial.

# O(1): In-place string reversal
left = 0
right = len(text) - 1
while left < right:
    text[left], text[right] = text[right], text[left]  # O(1)
    left += 1
    right -= 1

# O(n): Detect duplicate using hash set
seen_numbers = set()                                      # O(n)
for num in array:
    if num in seen_numbers:
        return True
    seen_numbers.add(num)

# O(log n): Recursive binary tree height
def tree_height(root):
    if not root:
        return 0
    return 1 + max(tree_height(root.left), tree_height(root.right))  # O(log n) stack

# O(n²): Floyd-Warshall distance matrix
distance = [[float('inf')] * vertices for _ in range(vertices)]  # O(n²)
for i in range(vertices):
    distance[i][i] = 0

Complejidad espacial frente a complejidad temporal Complejidad temporal

El tiempo y el espacio representan dimensiones de recursos distintas que deben equilibrarse en función de las limitaciones del sistema:

Diferencias y similitudes clave

A primera vista, la complejidad espacial y temporal pueden parecer similares, pero también son diferentes, ya que la complejidad temporal mide las operaciones computacionales, mientras que la complejidad espacial mide el consumo de memoria. Aunque ambos utilizan una notación asintótica y marcos de análisis matemático idénticos, debes saber que los algoritmos pueden ser óptimos en una dimensión e ineficaces en otra. La optimización suele implicar intercambiar un aumento de espacio por una reducción de tiempo, o viceversa.

Comprender la compensación fundamental

Cuando intercambias espacio por tiempo, estás almacenando resultados precalculados que eliminan cálculos redundantes. Por otro lado, cambiar tiempo por espacio requiere volver a calcular los valores bajo demanda en lugar de almacenarlos. Las tablas de consulta intercambian una inversión única de espacio por un acceso repetido O(1). Puede haber restricciones específicas, como límites de memoria y requisitos de rendimiento, que determinen qué recurso debe tener prioridad sobre otro.

Memorización y optimización de la programación dinámica

La memorización funciona guardando valores en lugar de volver a calcularlos; es eficiente en tiempo, pero ineficiente en espacio. Añade, por ejemplo, una caché O(n) al Fibonacci recursivo, pero reduce el tiempo de O(2^n) a O(n), como en el ejemplo siguiente sobre el Fibonacci memorizado, evitando el recálculo:

memory = {}
def fibonacci_memory(n):
    if n in memo:
        return memory[n] # O(n) space, O(n) time
    if n <= 1:
        return n
    memory[n] = fibonacci_memory(n-1) + fibonacci_memory(n-2)
    return memory[n]

Por otro lado, la programación dinámica ascendente realiza cálculos iterativos para eliminar la sobrecarga de la pila de recursión. Para optimizar el espacio, solo debes conservar los estados anteriores necesarios para el cálculo actual. Por ejemplo, la distancia de edición se puede reducir de una tabla O(nxm) a O(min(n,m)) conservando una fila.

Técnicas de algoritmos in situ

Los algoritmos in situ modifican directamente la entrada en lugar de asignar nuevas estructuras de memoria, lo que, si se repite, ayuda significativamente con la asignación de memoria y, por lo tanto, disminuye la complejidad del espacio, como se muestra en el siguiente ejemplo sobre la rotación de arreglos in situ (algoritmo de inversión):

def rotate_array(nums, k):
    n = len(nums)
    k = k % n
    reverse(nums, 0, k - 1)  # all operations O(1) auxiliary
    reverse(nums, k, n - 1)
    reverse(nums, 0, n - 1)

Otras técnicas integradas reducen drásticamente el uso de memoria. Por ejemplo, la técnica de dos punteros manipula arreglos con espacio auxiliar O(1), y la clasificación cíclica maneja problemas de permutación en espacio O(1) intercambiando elementos para corregir posiciones. Sin embargo, cabe señalar que la modificación in situ puede destruir los datos de entrada, lo que afecta a la reutilización y a la claridad del código.

Selección de la estructura de datos para optimizar el espacio

Existen muchas estructuras de datos diferentes, cada una de las cuales ofrece una compensación distinta; por lo tanto, por ejemplo, es preferible utilizar arreglos en lugar de listas enlazadas cuando se conoce el tamaño, eliminar la sobrecarga de punteros por elemento y manipular bits para almacenar indicadores booleanos con una compresión 8 veces mayor que las matrices de bytes. Los intentos comparten prefijos comunes para proporcionar eficiencia de espacio para grandes colecciones de cadenas. Para grafos dispersos, elige listas de adyacencia en lugar de matrices para obtener un espacio O(V+E) en lugar de O(V²).

Consideraciones prácticas y realidades de implementación

La complejidad espacial en el mundo real depende de los lenguajes de programación, la arquitectura del hardware y los entornos de ejecución.

Factores relacionados con el lenguaje y el entorno de ejecución

Los lenguajes de alto nivel como Python y Java añaden metadatos y sobrecarga por objeto, a diferencia de C y C++, que proporcionan una gestión manual de la memoria para un control preciso a costa de la complejidad. Probablemente por eso los marcos de optimización del machine learning, como PyTorch, utilizan C++ para los cálculos.

Los límites de tamaño de la pila suelen oscilar entre 1 y 8 MB, lo que limita la profundidad máxima de recursividad. Ten en cuenta que los sistemas de 64 bits utilizan punteros de 8 bytes, mientras que los de 32 bits utilizan punteros de 4 bytes, lo que duplica el tamaño de la estructura de los punteros. Para obtener más información sobre cómo los datos de alta dimensión afectan al rendimiento de los algoritmos, consulta nuestro tutorial «orial»: La maldición de la dimensionalidad en machine learning.

Jerarquía de memoria y efectos de caché

El uso del espacio del algoritmo y el rendimiento dependen en gran medida de la jerarquía de la memoria. El acceso a la RAM tarda unos 100 nanosegundos y el acceso a la caché de la CPU tarda entre 1 y 10 nanosegundos, lo que es 100 veces más rápido. Además, el acceso secuencial a la memoria aprovecha las líneas de caché, en las que normalmente se cargan 64 bytes juntos.

Los algoritmos con buena localidad espacial logran un mejor rendimiento gracias a la eficiencia de la caché. Por lo tanto, cuando se trabaja con conjuntos grandes que superan la capacidad, se produce un thrashing que degrada gravemente el rendimiento.

Recolección de basura y gestión de memoria

Una herramienta útil para la gestión de la memoria es la recolección de basura, que te permite limpiar los datos que ya no son útiles. En otras palabras, los recolectores de basura añaden una sobrecarga de memoria para el seguimiento de objetos y la gestión de la generación.

El uso máximo de memoria supera el tamaño de los datos activos debido a las asignaciones realizadas antes de los ciclos de recolección. Además, la GC generacional optimiza los objetos de corta duración manteniendo las generaciones jóvenes en espacios más pequeños. Sin embargo, si deseas un control más determinista del espacio, puedes utilizar la gestión manual de la memoria, pero debes ser consciente de sus riesgos, como las fugas de memoria y la fragmentación.

Conclusión y recomendaciones

Gracias por leer mi artículo sobre la complejidad espacial. Te dejo con algunos consejos finales:

• Siempre debes aclarar si el análisis del espacio incluye el tamaño de la entrada para evitar malentendidos en las entrevistas y revisiones de código.
• Prioriza primero la corrección y luego optimiza el espacio solo cuando el perfilado revele cuellos de botella reales.
• Intenta tener en cuenta las limitaciones de hardware y memoria en las primeras fases del diseño del sistema para evitar costosas refactorizaciones.
• Elige siempre las herramientas de perfilado adecuadas para el lenguaje con el fin de validar el análisis teórico frente al comportamiento real y equilibrar la optimización del espacio con la legibilidad del código. Las optimizaciones excesivamente ingeniosas también pueden perjudicar la facilidad de mantenimiento.