Complejidad espacial

La notación O grande indica cómo crece la memoria; esta calculadora te dice cuánta es en realidad: bytes, KB, MB y GB para n elementos de un tamaño dado.

Cómo funciona el cálculo

La complejidad espacial describe cómo aumenta el uso de memoria de un algoritmo al crecer la entrada. O(n) expresa el ritmo de crecimiento, no los megabytes. Aquí se calcula directamente el volumen útil: memoria = n × b, donde n es el número de elementos y b el tamaño de cada uno en bytes.

Valores habituales de b: 1 byte para char/uint8, 4 bytes para int32 y float, 8 bytes para int64, double y un puntero en 64 bits. El resultado usa unidades binarias: 1 KB = 1024 bytes, 1 MB = 2²⁰ = 1 048 576 bytes y 1 GB = 2³⁰ bytes (en rigor, KiB, MiB y GiB según IEC 80000-13).

Para otras estructuras, introduce en n el número real de elementos: n² para una matriz n×n, vértices más aristas para una lista de adyacencia. No se incluyen la sobrecarga de los contenedores ni el relleno por alineación.

Ejemplo resuelto

Un array de 1 000 000 de valores int32 (4 bytes): 1 000 000 × 4 = 4 000 000 bytes = 3906,3 KB ≈ 3,81 MB ≈ 0,004 GB. Si guardas los mismos valores como int64 o double (8 bytes) obtienes 8 000 000 bytes ≈ 7,63 MB, justo el doble.

Qué tener en cuenta

• Los valores «envueltos» cuestan mucho más: en CPython cada posición de una lista es un puntero de 8 bytes más un objeto int aparte (unos 28 bytes para números pequeños).
• Los arrays dinámicos (std::vector, ArrayList, list) reservan capacidad extra y las tablas hash dejan huecos libres a propósito: deja margen.
• Los algoritmos recursivos también consumen pila: profundidad de recursión × tamaño del marco forma parte de la complejidad espacial.
• Distingue espacio auxiliar (además de la entrada) y espacio total: merge sort necesita O(n) auxiliar; heapsort, O(1).