Complexidade de Espaço e Compromissos
Meça o espaço auxiliar das pilhas de chamadas e das estruturas de dados auxiliares e reconheça os compromissos entre tempo e espaço na memoização e nos algoritmos in-place.
Complexidade de Espaço e Compromissos é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
O que a complexidade espacial mede?
A complexidade espacial mede a memória extra além da entrada, chamada de espaço auxiliar. Algumas variáveis ocupam O(1); um vetor de resultados ou um mapa hash ocupa O(n). Consulte o código.
# O(1) auxiliary space
def sum_array(nums):
total = 0 # one integer variable
for n in nums:
total += n # constant extra space
return total
# O(n) auxiliary space
def copy_array(nums):
return list(nums) # allocates n slots
print(sum_array([1, 2, 3, 4])) # 10
print(copy_array([1, 2, 3, 4])) # [1, 2, 3, 4]Espaço da pilha de chamadas na recursão
Cada chamada recursiva adiciona um quadro à pilha, portanto a profundidade determina o espaço. A recursão linear é O(n); a DFS em uma árvore balanceada é O(log n). Uma versão iterativa pode controlar isso melhor.
import sys
def recursive_sum(n):
if n == 0: return 0
return n + recursive_sum(n - 1)
# Space: O(n) stack frames
def iterative_sum(n):
total = 0
while n > 0:
total += n
n -= 1
return total
# Space: O(1)
print(recursive_sum(100)) # 5050
print(iterative_sum(100)) # 5050Espaço da ordenação por intercalação: O(n)
A ordenação por intercalação precisa de O(n) de espaço extra para seus vetores temporários. Esse é o preço de uma ordenação estável O(n log n) — a ordenação por heap economiza espaço, mas não é estável. Consulte o código.
import tracemalloc
tracemalloc.start()
def merge_sort(arr):
if len(arr) <= 1: return arr
m = len(arr) // 2
l = merge_sort(arr[:m]) # new list
r = merge_sort(arr[m:]) # new list
out, i, j = [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: out.append(l[i]); i+=1
else: out.append(r[j]); j+=1
return out + l[i:] + r[j:]
data = list(range(1000, 0, -1))
merge_sort(data)
_, peak = tracemalloc.get_traced_memory()
print(f'Peak memory: {peak} bytes') # proportional to nAlgoritmos no próprio local: espaço O(1)
Um algoritmo no próprio local altera a entrada diretamente, sem armazenamento extra proporcional — como inverter um vetor com dois ponteiros. Assim, o espaço permanece em O(1). Consulte o código.
def reverse_inplace(arr):
l, r = 0, len(arr) - 1
while l < r:
arr[l], arr[r] = arr[r], arr[l] # swap
l += 1
r -= 1
# Space: O(1) -- only two pointer variables
def rotate_right(arr, k):
'''Rotate array right by k positions in-place.'''
n = len(arr)
k %= n
arr.reverse() # O(1) space
arr[:k] = arr[:k][::-1]
arr[k:] = arr[k:][::-1]
a = [1, 2, 3, 4, 5]
rotate_right(a, 2)
print(a) # [4, 5, 1, 2, 3]Compromisso entre tempo e espaço: dois-sum
O compromisso entre tempo e espaço aparece em toda parte. O problema de dois-sum usa O(n^2) de tempo e O(1) de espaço, ou O(n) de tempo e O(n) de espaço com um mapa hash. Mencione ambas as opções e pergunte o que é mais importante.
# O(n^2) time, O(1) space
def two_sum_slow(nums, target):
for i in range(len(nums)): # O(n)
for j in range(i+1, len(nums)): # O(n)
if nums[i] + nums[j] == target:
return [i, j]
return []
# O(n) time, O(n) space
def two_sum_fast(nums, target):
seen = {} # O(n) space
for i, n in enumerate(nums):
comp = target - n
if comp in seen: # O(1) lookup
return [seen[comp], i]
seen[n] = i
return []
print(two_sum_fast([2, 7, 11, 15], 9)) # [0, 1]Espaço da memoização versus tabulação
A memoização de cima para baixo custa O(n) para a memoização mais O(n) para a pilha; a tabulação de baixo para cima elimina a pilha. Manter apenas as últimas linhas reduz o espaço para O(1) — DP otimizada em espaço.
# Fibonacci: O(n) space with full table
def fib_table(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# O(1) space: keep only last two values
def fib_optimal(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_table(10)) # 55
print(fib_optimal(10)) # 55Espaço do mapa hash: O(n)
Um mapa hash é o custo usual de espaço O(n) nas soluções: um conjunto de elementos vistos para controlar os visitados e um mapa de frequências para fazer contagens. Sempre informe esse custo — «O(n) de tempo, O(n) de espaço» é a resposta completa.
def contains_duplicate(nums):
# O(n) time, O(n) space
seen = set()
for n in nums:
if n in seen: return True
seen.add(n)
return False
def group_anagrams(words):
# O(n*m) time, O(n) space (m = avg word length)
from collections import defaultdict
groups = defaultdict(list)
for w in words:
groups[tuple(sorted(w))].append(w)
return list(groups.values())
print(contains_duplicate([1,2,3,1])) # True
print(group_anagrams(['eat','tea','tan','ate','nat','bat']))Análise espacial para algoritmos de grafos
Os grafos exigem espaço real: uma lista de adjacência ocupa O(V + E), o conjunto de visitados e a fila da BFS ocupam O(V), e a recursão da DFS pode atingir O(V) de profundidade. Informe o espaço do grafo em termos de V e E.
from collections import deque
def bfs(graph, start):
# Space: O(V) for visited set + O(V) for queue
visited = set() # O(V)
queue = deque([start]) # O(V) max
order = []
while queue:
node = queue.popleft()
if node in visited: continue
visited.add(node)
order.append(node)
for nb in graph.get(node, []):
queue.append(nb)
return order
g = {0:[1,2], 1:[3], 2:[3], 3:[]}
print(bfs(g, 0)) # [0, 1, 2, 3]Armadilhas de alocação de strings e vetores
Alocações ocultas podem introduzir espaço O(n): o fatiamento cria uma nova lista, e + em strings dentro de um laço resulta em O(n^2). A função de ordenação cria uma cópia, mas lst.sort() permanece no próprio local. Consulte o código.
# Hidden allocations:
nums = [1, 2, 3, 4, 5]
# Creates a NEW list -- O(n) space
slice_copy = nums[1:4] # [2, 3, 4]
# Creates a NEW sorted list -- O(n) space
sorted_copy = sorted(nums) # nums unchanged
# Sorts IN PLACE -- O(1) extra space
nums.sort()
print(slice_copy) # [2, 3, 4]
print(sorted_copy) # [1, 2, 3, 4, 5]
print(nums) # [1, 2, 3, 4, 5]Reconhecendo compromissos de espaço em entrevistas
Informe sua complexidade espacial logo no início. Se o entrevistador quiser usar menos espaço, opções comuns são DP de baixo para cima em vez de memoização ou uma ordenação no próprio local em vez de um mapa hash. Consulte o código.
# Problem: find if array has duplicates
# Option 1: O(1) time-per-check, O(n) space
def has_dup_hash(nums):
return len(nums) != len(set(nums))
# Option 2: O(n log n) time, O(1) extra space
def has_dup_sort(nums):
nums_copy = sorted(nums) # O(n) space -- still!
for i in range(1, len(nums_copy)):
if nums_copy[i] == nums_copy[i-1]:
return True
return False
# Option 3: truly O(1) extra -- sort in-place
def has_dup_inplace(nums):
nums.sort() # modifies original
for i in range(1, len(nums)):
if nums[i] == nums[i-1]: return True
return FalseModelo para declarar a complexidade total
Sempre forneça a declaração completa — tempo e espaço: «O(n) de tempo, O(1) de espaço extra». Mencione os compromissos quando existirem. É isso que diferencia os candidatos mais experientes.
# Complete complexity example: Merge Intervals
def merge_intervals(intervals):
# Time: O(n log n) for sort + O(n) for merge = O(n log n)
# Space: O(n) for output (could be n/2 to n intervals)
intervals.sort(key=lambda x: x[0]) # O(n log n)
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]Verificação rápida
Verificação rápida — vamos ver como você assimilou as ideias sobre complexidade espacial. Você está preparado. ✅
Recapitulação da lição
Recapitulação: o espaço auxiliar é contado separadamente da entrada, a recursão usa espaço de pilha O(profundidade), e o compromisso entre tempo e espaço orienta a maioria das escolhas no projeto de algoritmos.
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “Complexidade de Espaço e Compromissos” é grátis?
Sim — o texto completo de “Complexidade de Espaço e Compromissos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Complexidade de Espaço e Compromissos”?
Meça o espaço auxiliar das pilhas de chamadas e das estruturas de dados auxiliares e reconheça os compromissos entre tempo e espaço na memoização e nos algoritmos in-place. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Complexidade de Espaço e Compromissos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Notação Big-O do Zero
- Analisando Laços e Laços Aninhados
- Recursão e o Método da Árvore de Recorrência
- Complexidade de Espaço e Compromissos