Complexidade espacial: Como os algoritmos usam a memória

A complexidade espacial mede o uso de memória dos algoritmos conforme o tamanho da entrada aumenta. Isso faz com que entender a complexidade do espaço seja importante para gerenciar recursos em ambientes com restrições.

Neste artigo, vou explicar em detalhes o que é complexidade espacial, como calculá-la e como minimizá-la. Além disso, vou falar sobre aplicações reais e oferecer fundamentos teóricos.

Entendendo a complexidade espacial

Antes de mergulhar nos cálculos e otimizações, vamos esclarecer o que realmente significa complexidade espacial e por que você deve se preocupar com isso.

O que é complexidade espacial?

A complexidade espacial é a quantidade total de memória que o algoritmo precisa em relação ao tamanho da entrada. Isso é importante pra analisar o pior caso de consumo de memória pra escalabilidade do sistema, e o espaço total inclui entrada, auxiliar e sobrecarga, enquanto o espaço auxiliar é a memória extra, excluindo entrada e saída. Pega, por exemplo, a classificação de uma matriz: O espaço total inclui a própria matriz, enquanto o espaço auxiliar pode ser o espaço temporário na classificação por mesclagem.

Por que a complexidade espacial é importante

Na computação moderna, a eficiência do espaço é muitas vezes fundamental. Ao otimizar a complexidade do espaço, você garante que seus algoritmos funcionem em dispositivos com pouca memória RAM, como sistemas integrados em IoT ou smartphones, ou até mesmo em grandes sistemas com procedimentos que exigem muitos recursos, onde cada bit de RAM é importante.

Pense nos aplicativos móveis como exemplo: otimizar a complexidade do espaço ajuda a evitar travamentos durante o processamento de imagens. Ou pense na economia de custos da computação em nuvem em armazenamento ou streaming de dados e na obtenção de análises em tempo real sem o carregamento completo dos dados.

Análise assintótica e notação Big O para espaço

Nesta seção, vou explicar como notações assintóticas como Big O descrevem o crescimento do espaço e te dar ferramentas para limitar e comparar o uso da memória.

Introdução à notação Big O

Matematicamente, uma função f(n) é dominada por uma função g(n) se existir uma constante c e k, de modo que para todos os k>n, 0 ≤ |f(n)| ≤ |g(n)|.

Nesse caso, escrevemos f(n)=O(g(n)), e dizemos que f(n) é grande O de g(n).

Em termos mais simples, isso quer dizer que f(n) não cresce mais rápido que g(n) a partir de um certo índice.

A notação Big O mostra o limite máximo de espaço como uma função do tamanho da entrada n, pra gente poder focar nos termos dominantes pra n grande.  Essa notação ajuda a classificar algoritmos, por exemplo, O(n) significa que o espaço dobra com a duplicação da entrada.

Tem um equívoco comum entre os iniciantes de que o Big O para espaço ignora constantes como 2n é O(n), mas, na prática, as constantes importam para n pequeno.

Notações assintóticas relacionadas

Existem diferentes maneiras de modelar a complexidade e diferentes notações. Por exemplo, o Big Omega dá um limite inferior que é útil pra provar que o espaço necessário é mínimo, tipo, a classificação precisa de pelo menos Ω(n). Outra notação é o Big Theta, que dá um limite apertado quando o superior e o inferior combinam, o que o torna ideal para análises precisas, como O(n) = Θ(n) para espaço linear.

Outras convenções de notação

Existem algumas outras convenções de notação relevantes para a literatura sobre complexidade espacial, como a notação Soft-O Õ, que ignora fatores polilógicos. É comum em algoritmos avançados, como processamento de gráficos, onde os registros são insignificantes. Aparece em artigos teóricos para complexidades aproximadas, como Õ para espaço sublinear em algoritmos de streaming.

Componentes da complexidade espacial

A complexidade espacial tem muitos fatores e pontos de otimização no design de algoritmos. Vamos ver:

Requisitos de espaço para entrada

Os dados de entrada ocupam espaço proporcional ao tamanho, como, por exemplo, O(n) para uma matriz ou para analisar um grande conjunto de dados, como sequências genômicas.

É comum em entrevistas de codificação do mundo real excluir o espaço de entrada ao calcular o espaço auxiliar e focar apenas na memória extra que o algoritmo usa. Na programação competitiva, no entanto, o espaço total geralmente inclui a entrada.

Espaço auxiliar e memória temporária

Espaço auxiliar é a memória extra que um algoritmo precisa para fazer suas operações. Isso afeta diretamente como o algoritmo é projetado.

Então, você pode, por exemplo, usar O(n) para a matriz temporária em um algoritmo de classificação por mesclagem. Outro exemplo seria as tabelas hash para duplicatas (O(n)), as pilhas de recursão para correspondência de parênteses (O(n)) e muitos outros.

Exemplos clássicos de espaço auxiliar incluem métodos de dois ponteiros (O(1)), algoritmos de janela deslizante usando uma fila dupla (O(k)) e BFS, que precisa de espaço O(V) para seu conjunto visitado e fila.

O código a seguir mostra um exemplo de uma operação para classificação por mesclagem na matriz temporária durante a etapa de mesclagem:

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...

A pilha de chamadas e o espaço de recursão

Cada chamada recursiva adiciona um quadro de pilha (endereço de retorno + parâmetros + variáveis locais).

Por outro lado, a recursão linear, como fatorial ou DFS em uma lista vinculada, tem uma pilha O(n).

A recursão binária, assim como a recursão ingênua de Fibonacci ou a recursão em árvore, tem um O(n) no pior cenário possível.

A otimização de chamadas de cauda, que é suportada em Scheme, Rust e, às vezes, Python com decoradores, reduz para O(1). Mas, o verdadeiro perigo aqui é o limite padrão de recursão do Python, que é de mais ou menos 1000, o que pode causar um estouro de pilha em árvores profundas.

Aqui está um exemplo de Fibonacci recursivo ingênuo que mostra o crescimento da pilha:

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

Dá uma olhada no nosso blog sobre Análise da complexidade do código através do Python para saber mais sobre a análise de complexidade do Python.

Sobrecarga da estrutura de dados

O bom da sobrecarga da estrutura de dados é a simplicidade, porque todas as estruturas têm custos fixos/por elemento, tipo a sobrecarga mínima de uma matriz, o espaço duplo dos ponteiros das listas vinculadas e muitos outros exemplos. 

De qualquer forma, a linguagem de programação tem uma influência enorme. As listas Python têm uma sobrecarga dinâmica, diferente das matrizes C — por exemplo, mapas hash com fator de carga de 75% desperdiçam espaço em colchetes vazios.

Tipos de complexidade espacial

Complexidade espacial constante: O(1)

A complexidade espacial constante é a solução fundamental e ideal, se encontrada. Muitos algoritmos conhecidos têm complexidade realmente constante, como trocas simples de variáveis, como no exemplo abaixo, que é uma troca simples no local usando o desempacotamento de tuplas Python:

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

Outros algoritmos conhecidos de complexidade constante são a partição da bandeira holandesa no quicksort e a travessia de Morris para árvores. Mas tem um limite prático em que você pode ter algumas dezenas de variáveis antes que isso seja eficaz, porque, dependendo do hardware do sistema, nos piores cenários, O(1) às vezes pode não ser suficiente se a memória necessária for maior do que os recursos do sistema.

Complexidade do espaço linear: O(n)

Uma complexidade espacial linear é simplesmente definida como sendo proporcional à entrada. Alguns exemplos seriam uma matriz extra para copiar ou um conjunto hash para valores únicos. O caso de uso mais comum está dentro dos padrões de processamento de dados, como filtrar listas.

Complexidade espacial logarítmica e sublinear

Uma complexidade espacial logarítmica significa que a quantidade de memória que um algoritmo usa cresce bem devagar conforme o tamanho da entrada aumenta. Especificamente, é proporcional ao logaritmo do tamanho da entrada.

Por exemplo, uma recursão de busca binária tem uma profundidade de pilha O(log(n)), assim como a divisão e conquista com recursão de cauda ou os algoritmos de streaming, que aproximam os resultados em espaço O(log(n)) ou O(sqrt(n)).

Complexidades logarítmicas e sublineares são raras, mas são muito poderosas para conjuntos de dados enormes. Você pode ver um exemplo de complexidade logarítmica com a pesquisa binária iterativa (espaço constante), como mostra o código de exemplo abaixo:

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

Complexidade espacial quadrática: O(n²)

Uma complexidade espacial quadrática rola quando a necessidade de memória aumenta com o quadrado da entrada. Um exemplo comum seria a tabela de programação dinâmica 2D, que tem uma complexidade de O(n²) ou uma matriz de adjacência para gráficos com complexidade O(V²). Mas é importante lembrar que essa complexidade fica meio complicada quando tem mais de mil elementos de entrada.

Complexidade exponencial e fatorial do espaço

A complexidade exponencial, como o nome já diz, faz com que o aumento de memória necessário seja proporcional ao tamanho da entrada elevado à potência O(2^n), e isso rola quando, por exemplo, você está guardando todos os subconjuntos ou caminhos da árvore de decisão.

Da mesma forma, na complexidade fatorial, a memória necessária é proporcional ao fatorial do tamanho da entrada O(n!), e isso acontece quando você está enumerando todas as permutações da entrada. Mas, essas complexidades geralmente são muito caras e quase sempre inviáveis para n>20-30 na maioria dos sistemas. Se você está trabalhando com isso, talvez precise mesmo de uma poda, aproximação ou uma abordagem diferente.

Como calcular a complexidade espacial

A análise sistemática identifica todas as alocações de memória e seus padrões de crescimento:

Abordagem de análise linha por linha

O primeiro passo é examinar seu código linha por linha e identificar todas as variáveis, matrizes e alocações de objetos. O próximo passo é ver se o tamanho de cada alocação depende dos parâmetros de entrada. Depois, some a memória para alocações independentes e pegue o máximo para ramificações mutuamente exclusivas. Por fim, você programa tanto as alocações de pilha para variáveis locais quanto as alocações de heap para memória dinâmica. Aqui vai um exemplo:

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álise de complexidade recursiva

A complexidade espacial para recursão é igual à profundidade máxima de recursão multiplicada pelo espaço por quadro de chamada, depois soma quaisquer estruturas de dados auxiliares alocadas durante a recursão, identifica o caso base e analisa como a profundidade da recursão se relaciona com o tamanho da entrada, como, por exemplo, Fibonacci ingênuo cria profundidade O(n) com O(1) por quadro, o que totaliza espaço de pilha O(n). Aqui está um exemplo de cálculo do espaço fatorial:

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

Análise da complexidade da programação dinâmica

As tabelas DP padrão têm dimensões que combinam com os parâmetros do subproblema; por isso, um problema unidimensional precisa de espaço O(n), e os problemas bidimensionais precisam de O(nxm). Técnicas de otimização como matrizes rolantes reduzem uma dimensão para transformar, por exemplo, O(n²) em O(n). A compactação de estado usa dependências, então se a linha i só precisa de i-1, basta guardar duas linhas. Aqui vai um exemplo de Fibonacci otimizado para espaço usando só duas variáveis:

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

Se você está curioso sobre dimensionalidade e sua redução, recomendo que dê uma olhada nos nossos tutoriais sobre Dominando dimensões que mudam lentamente (SCD) e Compreendendo a cardinalidade: Desafios e soluções para fluxos de trabalho com grande volume de dados.

Passos para calcular a complexidade espacial na prática

Para calcular a complexidade do espaço na prática, siga estas etapas:

1. Esclareça se o espaço de entrada está incluído com base no contexto.
2. Conte variáveis e constantes de tamanho fixo. Eles contribuem com O(1)
3. Meça estruturas auxiliares, como matrizes e mapas hash, em relação ao tamanho da entrada.
4. Calcule a profundidade máxima de recursão para a contribuição do espaço da pilha
5. Junte todos os componentes e expresse usando o limite assintótico mais restrito.

A complexidade espacial dos algoritmos comuns

Requisitos de espaço do algoritmo de classificação

O algoritmo de ordenação por mesclagem precisa de espaço auxiliar O(n) para matrizes temporárias durante a mesclagem. Por outro lado, o Quicksort usa só O(log n) de espaço médio na pilha, mas O(n) no pior caso sem otimização. Enquanto a classificação por pilha só consegue espaço auxiliar O(1) ao classificar no local, como mostra o código a seguir:

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 fim, a classificação por contagem precisa de espaço O(k), onde k é o intervalo de valores, mas não é prático quando k>>n.

Complexidade espacial do algoritmo gráfico

A travessia de grafos tem vários algoritmos. Por exemplo, a busca em largura (BFS) mantém uma fila que precisa de espaço O(V) para vértices, enquanto a busca em profundidade (DFS) usa espaço de pilha O(V) no pior caso para profundidade máxima.  Já o algoritmo de Dijkstra precisa de O(V) para a fila de prioridade e o rastreamento de distância para cada um. A representação gráfica é importante porque a matriz de adjacência usa O(V²), enquanto a lista de adjacência usa O(V+E). 

Características do espaço da estrutura de dados

Existem diferentes estruturas de dados e cada uma precisa de uma quantidade diferente de memória. Por exemplo, matrizes e listas de matrizes armazenam n elementos em memória contígua O(n), listas vinculadas precisam de espaço O(n) mais sobrecarga de ponteiro para cada nó, árvores binárias usam espaço O(n) com 2-3 ponteiros por nó, o que adiciona uma sobrecarga significativa, tabelas hash consomem espaço O(n) multiplicado pelo fator de carga que normalmente varia entre 1,5 e 3 vezes, e as listas de adjacência fornecem eficiência de espaço O(V+E) para grafos esparsos.

Exemplos de cálculos de complexidade espacial

Aqui estão alguns exemplos para o cálculo da complexidade 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

Complexidade espacial vs. Complexidade temporal

Tempo e espaço são dimensões de recursos diferentes que precisam ser equilibradas com base nas limitações do sistema:

Principais diferenças e semelhanças

No começo, a complexidade espacial e temporal podem parecer parecidas, mas também são diferentes porque a complexidade temporal mede as operações computacionais, enquanto a complexidade espacial mede o consumo de memória. Embora ambos usem notação assintótica e estruturas de análise matemática idênticas, é importante saber que os algoritmos podem ser ótimos em uma dimensão e ineficientes em outra. A otimização geralmente envolve trocar mais espaço por menos tempo ou vice-versa.

Entendendo a relação fundamental entre vantagens e desvantagens

Quando você troca espaço por tempo, você está guardando resultados pré-calculados que eliminam cálculos desnecessários. Por outro lado, trocar tempo por espaço exige recalcular os valores quando precisar, em vez de guardá-los. As tabelas de pesquisa trocam um investimento único de espaço por acesso repetido O(1). Pode ter restrições específicas, tipo limites de memória e requisitos de desempenho, que decidem qual recurso deve ser priorizado em relação ao outro.

Memorização e otimização da programação dinâmica

A memorização funciona salvando valores em vez de recalculá-los; é eficiente em termos de tempo, mas ruim em termos de espaço. Isso adiciona, por exemplo, cache O(n) ao Fibonacci recursivo, mas reduz o tempo de O(2^n) para O(n), como no exemplo abaixo sobre Fibonacci memorizado, evitando o 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]

Já a programação dinâmica bottom-up faz cálculos iterativos pra eliminar a sobrecarga da pilha de recursão. Para otimizar o espaço, você deve manter apenas os estados anteriores necessários para o cálculo atual, como, por exemplo, a distância de edição pode ser reduzida de uma tabela O(nxm) para O(min(n,m)) mantendo uma linha.

Técnicas de algoritmos no local

Os algoritmos no local modificam a entrada diretamente, em vez de alocar novas estruturas de memória, o que, se repetido, ajuda bastante na alocação de memória e, assim, diminui a complexidade do espaço, como no exemplo abaixo sobre rotação de matriz no local (algoritmo de reversão):

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)

Outras técnicas já existentes diminuem bastante o uso de memória. Por exemplo, a técnica de dois ponteiros mexe em matrizes com espaço auxiliar O(1), e a classificação cíclica resolve problemas de permutação em espaço O(1) trocando elementos para as posições certas. Mas, vale a pena notar que a modificação no local pode acabar com os dados de entrada, afetando a reutilização e a clareza do código.

Escolha da estrutura de dados para aproveitar melhor o espaço

Tem várias estruturas de dados diferentes, cada uma com suas vantagens e desvantagens; por isso, por exemplo, é melhor usar matrizes em vez de listas encadeadas quando o tamanho é conhecido, eliminar a sobrecarga do ponteiro por elemento e manipular bits para armazenar sinalizadores booleanos com compressão 8 vezes maior em comparação com matrizes de bytes. As tentativas compartilham prefixos comuns para proporcionar eficiência de espaço para grandes coleções de strings. Para gráficos esparsos, escolha listas de adjacência em vez de matrizes para obter espaço O(V+E) em vez de O(V²).

Considerações práticas e realidades da implementação

A complexidade espacial no mundo real depende das linguagens de programação, da arquitetura do hardware e dos ambientes de tempo de execução.

Fatores relacionados à linguagem e ao ambiente de execução

Linguagens de alto nível como Python e Java adicionam metadados e sobrecarga por objeto, ao contrário do C e do C++, que oferecem gerenciamento manual de memória para um controle preciso, mas com um pouco mais de complexidade. É por isso que as estruturas de otimização de machine learning, como o PyTorch, usam C++ para fazer cálculos.

Os limites de tamanho da pilha geralmente variam de 1 a 8 MB, o que limita a profundidade máxima de recursão. Observe que os sistemas de 64 bits usam ponteiros de 8 bytes, enquanto os de 32 bits usam ponteiros de 4 bytes, o que dobra o tamanho da estrutura do ponteiro. Pra saber mais sobre como os dados de alta dimensão afetam o desempenho dos algoritmos, dá uma olhada no nosso tutorial:orial: A maldição da dimensionalidade no machine learning.

Hierarquia de memória e efeitos do cache

O uso do espaço do algoritmo e o desempenho dependem muito da hierarquia da memória. O acesso à RAM leva cerca de 100 nanossegundos e o acesso ao cache da CPU leva de 1 a 10 nanossegundos, o que é 100 vezes mais rápido. Além disso, o acesso sequencial à memória usa as linhas de cache, onde normalmente 64 bytes são carregados juntos.

Algoritmos com boa localidade espacial têm um desempenho melhor por causa da eficiência do cache. Então, quando você tá trabalhando com conjuntos grandes que ultrapassam a capacidade, isso causa thrashing, o que prejudica bastante o desempenho.

Coleta de lixo e gerenciamento de memória

Uma ferramenta útil para gerenciamento de memória é a coleta de lixo, que permite limpar dados que não são mais úteis. Ou seja, os coletores de lixo aumentam a sobrecarga de memória para rastreamento de objetos e gerenciamento de geração.

O pico de uso de memória ultrapassa o tamanho dos dados ativos por causa das alocações feitas antes dos ciclos de coleta. Além disso, o GC geracional otimiza objetos de curta duração, mantendo as gerações jovens em espaços menores. Mas, se você quiser um controle mais preciso do espaço, pode usar o gerenciamento manual da memória, mas é bom ficar atento aos riscos, como vazamentos e fragmentação de memória.

Conclusão e recomendações

Valeu por ler meu artigo sobre complexidade espacial. Vou deixar algumas dicas finais:

• Você deve sempre deixar claro se a análise de espaço inclui o tamanho da entrada para evitar mal-entendidos nas entrevistas e revisões de código.
• Priorize a correção primeiro e só otimize o espaço quando a análise revelar gargalos reais.
• Tente pensar nas limitações de hardware e memória logo no começo do projeto do sistema pra evitar refatorações caras.
• Sempre escolha as ferramentas de perfilagem certas para o idioma pra validar a análise teórica em relação ao comportamento real e equilibrar a otimização do espaço com a legibilidade do código. Otimizações muito inteligentes também podem prejudicar a manutenção.