Notación Big-O: complejidad espacial

Optimizing Code in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

¿Qué es la complejidad espacial?

La complejidad temporal describe cómo el tamaño de entrada afecta al tiempo de ejecución
La complejidad espacial describe cómo el tamaño de entrada afecta al uso de memoria

Entender la complejidad espacial es clave para crear aplicaciones que:

Usen solo la memoria necesaria, sin exceso
Eviten fallos como OutOfMemoryError

Notación Big-O

La notación es idéntica a la de complejidad temporal.

Clases comunes de complejidad:

O(1): Constante: independiente del tamaño
O(n): Lineal: crece con la entrada
O(n²): Cuadrática: crece cuadráticamente con la entrada

Un método para encontrar el máximo

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

Tenga nuestro array 10 o 10 millones de enteros, solo usamos memoria para una variable, max
La complejidad espacial es O(1) o constante

Un método que duplica valores

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

Si la entrada tiene n elementos, necesitamos espacio para n elementos adicionales
La complejidad espacial es O(n) porque la memoria extra crece linealmente con el tamaño de entrada

Un método de tabla de multiplicar

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

Si n es 10, necesitamos 100 celdas; si n es 100, necesitamos 10.000 celdas
Lo clasificamos como O(n²)

¿Por qué importa la complejidad espacial?

¡La memoria es un recurso finito!

Nuestros ejemplos anteriores con tamaño de entrada 10.000 elementos:

findMax, O(1) -> solo unos pocos bytes extra
doubleValues, O(n) -> unos 40 KB de memoria extra
multiplicationTable, O(n²) -> alrededor de 400 MB de memoria extra

Gráfico de barras que muestra un aumento de 8 bytes en findMax, 40 KB en doubleValues y 400 MB en multiplicationTable

Complejidad espacial vs. complejidad temporal

No lo olvides:

A veces intercambiamos espacio por tiempo
A veces intercambiamos tiempo por espacio
La elección adecuada depende de tus limitaciones concretas

Gráficos que simbolizan el equilibrio entre tiempo y espacio

¡Vamos a practicar!

Optimizing Code in Java