Complexidade espacial

A notação Big-O mostra como a memória cresce; esta calculadora mostra quanto ela realmente ocupa — bytes, KB, MB e GB para n elementos de um tamanho dado.

Como funciona o cálculo

Complexidade espacial descreve como o uso de memória de um algoritmo aumenta com o tamanho da entrada. O(n) indica o ritmo de crescimento, não os megabytes. Aqui o volume útil é calculado diretamente: memória = n × b, em que n é o número de elementos e b o tamanho de cada um em bytes.

Valores comuns de b: 1 byte para char/uint8, 4 bytes para int32 e float, 8 bytes para int64, double e ponteiro em 64 bits. O resultado usa unidades binárias: 1 KB = 1024 bytes, 1 MB = 2²⁰ = 1.048.576 bytes e 1 GB = 2³⁰ bytes (a rigor, KiB, MiB e GiB pela IEC 80000-13).

Para outras estruturas, coloque em n a contagem real de elementos: n² para uma matriz n×n, vértices mais arestas para uma lista de adjacência. Overhead dos contêineres e preenchimento por alinhamento não entram no cálculo.

Exemplo resolvido

Um array de 1.000.000 de valores int32 (4 bytes): 1.000.000 × 4 = 4.000.000 bytes = 3.906,3 KB ≈ 3,81 MB ≈ 0,004 GB. Guardando os mesmos valores como int64 ou double (8 bytes), são 8.000.000 bytes ≈ 7,63 MB — exatamente o dobro.

Pontos de atenção

• Valores encapsulados custam bem mais: no CPython cada posição de uma lista é um ponteiro de 8 bytes mais um objeto int separado (cerca de 28 bytes para números pequenos).
• Arrays dinâmicos (std::vector, ArrayList, list) reservam capacidade extra e tabelas hash mantêm posições vazias de propósito — deixe folga.
• Algoritmos recursivos também usam a pilha: profundidade da recursão × tamanho do quadro conta na complexidade espacial.
• Diferencie espaço auxiliar (além da entrada) de espaço total: merge sort precisa de O(n) auxiliar; heapsort, de O(1).