Complexidade de espaço + quiz da seção
Tempo é metade da história. A outra metade — quanta memória extra sua solução usa — decide entre duas soluções igualmente rápidas e aparece em toda entrevista: "dá para fazer com O(1) de espaço?"
O que conta como espaço
A complexidade de espaço mede a memória extra que o algoritmo aloca, além da entrada que ele recebeu:
- A entrada em si não conta (ela já existia).
- Variáveis soltas (
i,soma,melhor) custam O(1) — não crescem com n. - Uma cópia do array, um hash map que pode guardar todos os elementos, uma lista de resultados do tamanho da entrada: O(n).
- Uma matriz n × n: O(n²).
def soma(nums): # espaço O(1):
total = 0 # uma variável, qualquer que seja n
for x in nums:
total += x
return total
def dobrados(nums): # espaço O(n):
resultado = [] # cresce junto com a entrada
for x in nums:
resultado.append(x * 2)
return resultado
O trade-off tempo × espaço
Esta é uma das ideias mais importantes do curso inteiro: muitas vezes você compra tempo pagando com memória.
Lembra do exemplo da aula 1? Detectar duplicados em O(n²) usa espaço O(1); a versão O(n) usa um set que pode guardar todos os elementos — espaço O(n). Não existe almoço grátis: a versão rápida paga com memória.
| Solução | Tempo | Espaço |
|---|---|---|
| Comparar todos os pares | O(n²) 🐢 | O(1) 💚 |
| Set de já vistos | O(n) 🚀 | O(n) 💸 |
No LeetCode esse trade quase sempre vale a pena (limites de memória são generosos), e é exatamente o que o padrão hash map faz — primeira aula da seção Array.
Espaço escondido: a pilha da recursão
Quando uma função chama a si mesma, cada chamada pendente ocupa memória na pilha de execução. Uma recursão que se aprofunda n níveis usa O(n) de espaço mesmo sem criar nenhuma lista! Guarde essa ideia — ela volta com força nas seções de Árvores e Programação Dinâmica.
Quiz da seção — Fundamentos
Este quiz fecha a seção. Se acertar 7 ou mais, você está pronto para a seção Array. Qualquer dúvida, as três aulas estão aí — reler é parte do método.
🧠 Quiz da seção: Big-O
0/81. O que o Big-O de um algoritmo descreve?
2. Por que O(2n + 100) é simplificado para O(n)?
3. for i in range(n): for j in range(i + 1, n): comparar(i, j) Qual o Big-O?
4. Ordenar o array e depois fazer uma única passada por ele custa, no total:
5. Buscar um valor com `x in minha_lista` (lista de n itens, sem ordenação) custa:
6. Uma solução usa apenas as variáveis `i`, `melhor` e `atual`, qualquer que seja o tamanho do array. O espaço extra é:
7. Uma solução O(n) de tempo usa um hash map que pode guardar todos os n elementos. Outra é O(n²) de tempo com espaço O(1). Para n = 100.000 no LeetCode, qual escolher e por quê?
8. Uma função recursiva se chama n vezes em profundidade (cada chamada espera a próxima). Mesmo sem criar listas, o espaço é:
Resumo da seção
Você agora tem o vocabulário que o curso inteiro usa:
- Big-O = forma do crescimento, com pior caso, sem constantes.
- Sequência soma, aninhamento multiplica, metade vira log.
- Operações prontas têm custo escondido (
inde lista = O(n), sort = O(n log n)). - Espaço extra conta — e trocar memória por tempo (hash map) é o trade mais lucrativo do LeetCode.
Agora sim: seção Array, onde esses fundamentos viram padrões de resolução.