Analise a complexidade de tempo e de espaço
Descreva como o tempo de execução e a memória crescem com o tamanho da entrada.
- Descrever algoritmos com a notação Big O.
- Reconhecer as classes de complexidade mais comuns.
- Trocar memória por velocidade de forma deliberada.
O Big O descreve como o custo de um algoritmo cresce conforme o tamanho da entrada n cresce, ignorando fatores constantes. Os entrevistadores esperam que você diga a complexidade de tempo e de espaço de toda solução que propuser, e que explique por quê. É também assim que você sabe se uma solução é rápida o bastante: com n = 100.000, um algoritmo O(n²) faz 10 bilhões de passos; um O(n log n) faz cerca de 1,7 milhão.
Classes de complexidade comuns
- O(1) constante: indexar uma lista, uma busca num dict (em média).
- O(log n) logarítmica: busca binária - o problema cai pela metade a cada passo.
- O(n) linear: uma passada pela entrada.
- O(n log n): ordenação eficiente.
- O(n²) quadrática: laços aninhados sobre a entrada.
- O(2ⁿ) exponencial: testar todos os subconjuntos.
A complexidade de espaço conta a memória extra. Muitas otimizações trocam espaço por tempo: guardar o que você já viu num set transforma varreduras O(n) repetidas em buscas O(1).
1nums = [4, 1, 7, 1]
2
3# O(n^2) time, O(1) space: compare every pair
4pairs = any(nums[i] == nums[j] for i in range(len(nums)) for j in range(i + 1, len(nums)))
5
6# O(n) time, O(n) space: remember what we have seen
7seen, found = set(), False
8for num in nums:
9 if num in seen:
10 found = True
11 seen.add(num)
12
13print(pairs, found)True True
Quando analisar código, conte os laços e o que acontece dentro deles. Um laço sobre n itens que faz uma busca O(1) num dict é O(n). Um laço que chama list.index ou x in some_list lá dentro está escondendo um segundo laço O(n), o que torna o todo O(n²). Descarte as constantes e os termos de menor ordem: O(2n + 5) é O(n).
Principais conclusões
O Big O descreve o crescimento, ignorando constantes e termos menores.
Laços aninhados sobre a entrada costumam significar O(n²).
Hash sets e hash maps trocam O(n) de memória por buscas O(1) em média.
Quiz da aula
6 perguntas · aprovação com 5 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Detecte duplicatas em O(n)
Leia uma linha de inteiros separados por espaços. Imprima true se algum valor aparecer mais de uma vez; caso contrário, false. Busque tempo O(n) usando um set.
- Tem uma duplicata
- Todos distintos
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…