📊 Complexidade de Espaço (Auxiliar)

Quando falamos de complexidade, muita gente pensa primeiro em tempo. Mas memória também importa.

Um algoritmo pode ser rápido e, ainda assim, usar memória demais. É por isso que também analisamos complexidade de espaço.

O foco aqui é um conceito mais específico:

espaço auxiliar.

O que é espaço auxiliar?

Espaço auxiliar é a memória extra que o algoritmo usa além da própria entrada.

Essa distinção é importante.

Por exemplo:

• se a entrada já é uma lista com n elementos, essa lista faz parte do problema
• mas se o algoritmo cria outra estrutura de tamanho n para ajudar no processamento, isso conta como memória extra

Espaço auxiliar é a memória que o algoritmo precisa para trabalhar, além dos dados que já recebeu.

Um exemplo simples: soma de elementos

def somar(lista):
    total = 0
    for num in lista:
        total += num
    return total

Aqui, além da lista de entrada, usamos apenas:

• total
• num

Essas variáveis ocupam uma quantidade fixa de memória.

Por isso, o espaço auxiliar é:

O(1)

Exemplo com memória extra proporcional a n

Agora veja este caso:

def copiar_lista(lista):
    nova_lista = []
    for item in lista:
        nova_lista.append(item)
    return nova_lista

Além da entrada, criamos uma nova lista que cresce junto com n.

Nesse caso, o espaço auxiliar é:

O(n)

Estruturas auxiliares também contam

Sempre que criamos estruturas extras para ajudar na solução, elas entram na conta.

Exemplos:

• arrays auxiliares
• conjuntos (set)
• mapas (dict)
• pilhas ou filas criadas pelo próprio algoritmo

Se a estrutura extra cresce com a entrada, o espaço auxiliar também cresce.

Exemplo: detectar duplicatas com conjunto

def tem_duplicata(lista):
    vistos = set()
    for item in lista:
        if item in vistos:
            return True
        vistos.add(item)
    return False

Esse algoritmo costuma ser eficiente em tempo, mas usa memória extra para armazenar os elementos já vistos.

No pior caso, o conjunto pode guardar até n elementos.

Logo, o espaço auxiliar é:

O(n)

Tempo e espaço podem trocar favores

Em muitos problemas, existe uma troca entre tempo e espaço.

Por exemplo:

• uma solução pode usar mais memória para evitar trabalho repetido
• outra pode usar menos memória, mas gastar mais tempo

Essa troca aparece o tempo todo em algoritmos.

Então, escolher a melhor solução nem sempre significa escolher apenas a menor complexidade de tempo.

E a entrada, entra na conta?

Depende do que estamos medindo.

Se estivermos falando de espaço total, podemos considerar:

• entrada
• variáveis
• estruturas auxiliares
• pilha de chamadas

Mas quando falamos em espaço auxiliar, normalmente queremos isolar apenas a memória extra criada pela solução.

Essa é a convenção mais útil na comparação entre algoritmos.

Recursão também consome espaço

Mesmo sem criar arrays ou conjuntos extras, um algoritmo recursivo pode usar memória na pilha de chamadas.

Exemplo:

def contar(n):
    if n == 0:
        return
    contar(n - 1)

Cada chamada fica armazenada até a recursão terminar.

Se a profundidade for proporcional a n, o espaço auxiliar da pilha pode ser:

O(n)

Esse ponto é importante porque, às vezes, a memória extra não aparece em variáveis visíveis no código.

Como pensar rapidamente sobre espaço auxiliar

Ao analisar um algoritmo, faça perguntas como:

• criei alguma estrutura extra?
• essa estrutura cresce com n?
• estou usando recursão?
• quantas chamadas ficam empilhadas ao mesmo tempo?

Essas perguntas ajudam bastante a estimar o uso de memória.

Resumo

• Espaço auxiliar é a memória extra usada pelo algoritmo além da entrada.
• Variáveis fixas costumam levar a O(1) de espaço auxiliar.
• Estruturas extras que crescem com n costumam levar a O(n).
• Recursão também pode consumir espaço por causa da pilha de chamadas.
• Em muitos problemas, existe troca entre tempo e espaço.

Esse tipo de análise complementa a complexidade de tempo e ajuda a comparar soluções que fazem trocas diferentes entre memória e processamento.