Complexidade de Algoritmos e Notação Big-O
A complexidade mede como o tempo de execução ou uso de memória cresce conforme o tamanho da entrada (n). A notação Big-O descreve o pior caso.
| Notação | Nome | Exemplo | n=1000 |
|---|
| O(1) | Constante | Acessar lista[i] | 1 op |
| O(log n) | Logarítmica | Busca binária | ~10 ops |
| O(n) | Linear | Percorrer lista | 1.000 ops |
| O(n log n) | Linearítmica | Merge Sort | ~10.000 ops |
| O(n²) | Quadrática | Bubble Sort | 1.000.000 ops |
| O(2ⁿ) | Exponencial | Subconjuntos | inviável |
⚠ Regra prática
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Em entrevistas, sempre justifique a complexidade do seu algoritmo.
Como calcular Big-O
1. Loop simples de 0 a n → O(n)
2. Loop dentro de loop (ambos até n) → O(n²)
3. Dividir o problema pela metade a cada passo → O(log n)
4. Constantes e termos menores são ignorados: O(3n + 5) = O(n)
# O(n) — percorre uma vez
def soma_lista(lst):
total = 0
for x in lst: # n iterações
total += x # O(1)
return total # total: O(n)
# O(n²) — loop aninhado
def tem_duplicata(lst):
for i in range(len(lst)): # n
for j in range(i+1, len(lst)): # n
if lst[i] == lst[j]:
return True
return False # O(n²)
# O(n) com set — muito melhor!
def tem_duplicata_rapido(lst):
return len(lst) != len(set(lst)) # O(n)
Espaço vs Tempo
Complexidade de tempo = quantas operações. Complexidade de espaço = quanta memória extra usa. Frequentemente há um trade-off entre os dois.
Exercício 1: Qual a complexidade de buscar um elemento em uma lista não ordenada?
→ O(n) — pior caso: percorre tudo sem encontrar.
Tem que checar cada elemento um a um. Não tem como pular.
Exercício 2: Qual a complexidade de acessar um dicionário Python por chave?
→ O(1) médio — dicionário é uma tabela hash internamente.
Hash mapeia a chave diretamente para a posição. Por isso dicionários são preferíveis a listas para busca.
Algoritmos de Ordenação
| Algoritmo | Melhor | Médio | Pior | Estável? | Quando usar |
|---|
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Sim | Dados grandes, garantia de desempenho |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | Não | Prática — rápido na maioria dos casos |
| Insertion Sort | O(n) | O(n²) | O(n²) | Sim | Listas pequenas ou quase ordenadas |
| Bubble Sort | O(n) | O(n²) | O(n²) | Sim | Só didático — nunca em produção |
| Selection Sort | O(n²) | O(n²) | O(n²) | Não | Só didático |
# Merge Sort em Python — O(n log n)
def merge_sort(lst):
if len(lst) <= 1:
return lst
meio = len(lst) // 2
esq = merge_sort(lst[:meio])
dir = merge_sort(lst[meio:])
return merge(esq, dir)
def merge(esq, dir):
resultado = []
i = j = 0
while i < len(esq) and j < len(dir):
if esq[i] <= dir[j]:
resultado.append(esq[i]); i += 1
else:
resultado.append(dir[j]); j += 1
return resultado + esq[i:] + dir[j:]
# Quick Sort em Python — O(n log n) médio
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivo = lst[len(lst) // 2]
esq = [x for x in lst if x < pivo]
meio = [x for x in lst if x == pivo]
dir = [x for x in lst if x > pivo]
return quick_sort(esq) + meio + quick_sort(dir)
# Python nativo — use sempre que possível!
lista = [3,1,4,1,5,9,2,6]
lista.sort() # in-place, O(n log n) — Timsort
sorted(lista) # retorna nova lista
⚠ Python usa Timsort
O método
sort() e a função
sorted() do Python usam Timsort — híbrido de Merge Sort e Insertion Sort. É O(n log n) garantido e estável. Sempre prefira ao implementar do zero.
Exercício 3: Por que Quick Sort é O(n²) no pior caso?
→ Quando o pivô escolhido é sempre o menor ou maior elemento (lista já ordenada).
Cada partição fica com n-1 e 0 elementos — gera n recursões de tamanho n-1, n-2... = O(n²). Escolher pivô aleatório ou do meio minimiza esse risco.
Busca e Recursão
Busca Linear vs Busca Binária
# Busca Linear — O(n) — funciona em qualquer lista
def busca_linear(lst, alvo):
for i, v in enumerate(lst):
if v == alvo:
return i
return -1
# Busca Binária — O(log n) — EXIGE lista ORDENADA
def busca_binaria(lst, alvo):
esq, dir = 0, len(lst) - 1
while esq <= dir:
meio = (esq + dir) // 2
if lst[meio] == alvo:
return meio
elif lst[meio] < alvo:
esq = meio + 1
else:
dir = meio - 1
return -1
# Python nativo
import bisect
lst = [1, 3, 5, 7, 9, 11]
idx = bisect.bisect_left(lst, 7) # busca binária nativa
⚠ Busca Binária exige ordenação
Busca binária é O(log n) mas só funciona em listas ordenadas. Se a lista não está ordenada: ordenar (O(n log n)) + buscar (O(log n)) = O(n log n). Para uma busca só, busca linear é melhor. Para muitas buscas, vale ordenar uma vez.
Recursão
Uma função recursiva chama a si mesma com um problema menor. Toda recursão precisa de: (1) caso base — para de chamar; (2) caso recursivo — reduz o problema.
# Fatorial — O(n)
def fatorial(n):
if n <= 1: # caso base
return 1
return n * fatorial(n - 1) # caso recursivo
# Fibonacci — O(2ⁿ) ingênuo, O(n) com memoização
def fib(n, memo={}):
if n <= 1: return n
if n not in memo:
memo[n] = fib(n-1, memo) + fib(n-2, memo)
return memo[n]
# Fibonacci — O(n) com programação dinâmica
def fib_dp(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# Soma de lista recursiva
def soma(lst):
if not lst: return 0 # caso base
return lst[0] + soma(lst[1:]) # caso recursivo
⚠ Stack Overflow
Cada chamada recursiva ocupa espaço na pilha. Recursão muito profunda causa
RecursionError em Python (limite padrão: 1000 chamadas). Para problemas grandes, prefira versão iterativa ou use
memoização.
Programação Dinâmica
Técnica que resolve subproblemas menores e armazena os resultados para não recalcular. Transforma O(2ⁿ) em O(n).
Exercício 4: Qual a diferença entre recursão com memoização e programação dinâmica bottom-up?
→ Memoização (top-down): começa do problema grande, armazena resultados conforme desce. Bottom-up: começa dos casos base e vai subindo.
Ambas têm O(n) de tempo. Bottom-up evita overhead de chamadas recursivas e risco de stack overflow — preferível para n grande.
Python Essencial para Backend e AI
Estruturas de Dados em Python
# Lista — O(1) append, O(n) busca
lst = [1, 2, 3]
lst.append(4) # O(1)
lst.insert(0, 0) # O(n) — desloca tudo
lst.pop() # O(1) — remove o último
lst.pop(0) # O(n) — remove o primeiro
# Dicionário — O(1) médio para tudo
d = {'a': 1, 'b': 2}
d['c'] = 3 # inserir
d.get('x', 0) # buscar com default
d.items() # pares (chave, valor)
# Set — O(1) médio, sem duplicatas
s = {1, 2, 3}
s.add(4)
s.discard(1)
inter = s & {2, 4} # interseção
# Deque — O(1) nas duas extremidades (use como fila/pilha)
from collections import deque
fila = deque()
fila.append(1) # enqueue — O(1)
fila.appendleft(0) # O(1) — lista seria O(n)
fila.popleft() # dequeue — O(1)
Python Avançado — Ferramentas que Importam
# List comprehension — Pytônico e eficiente
quadrados = [x**2 for x in range(10)]
pares = [x for x in range(20) if x % 2 == 0]
# Dict comprehension
freq = {c: s.count(c) for c in set(s)}
# Generator — lazy, não carrega tudo na memória
gen = (x**2 for x in range(10**6)) # não ocupa memória
next(gen) # calcula um por vez
# Funções de ordem superior
nums = [3, 1, 4, 1, 5]
list(map(lambda x: x*2, nums)) # aplica função
list(filter(lambda x: x>2, nums)) # filtra
from functools import reduce
reduce(lambda a,b: a+b, nums) # reduz
# Sorted com chave customizada
pessoas = [('Ana',25), ('Bia',22), ('Carlos',30)]
sorted(pessoas, key=lambda p: p[1]) # ordena por idade
# Counter — contar frequências
from collections import Counter
c = Counter('abracadabra')
c.most_common(3) # [('a',5),('b',2),('r',2)]
# Defaultdict — evita KeyError
from collections import defaultdict
grafo = defaultdict(list)
grafo['A'].append('B') # sem verificar se 'A' existe
Algoritmos Clássicos em Python
# Dois ponteiros — O(n), para listas ordenadas
def dois_ponteiros(lst, alvo):
esq, dir = 0, len(lst) - 1
while esq < dir:
soma = lst[esq] + lst[dir]
if soma == alvo: return (esq, dir)
elif soma < alvo: esq += 1
else: dir -= 1
return None
# Sliding window — O(n), janela deslizante
def max_soma_subarray(lst, k):
soma = sum(lst[:k])
maximo = soma
for i in range(k, len(lst)):
soma += lst[i] - lst[i-k]
maximo = max(maximo, soma)
return maximo
# BFS — busca em largura em grafo
from collections import deque
def bfs(grafo, inicio):
visitados = set()
fila = deque([inicio])
while fila:
no = fila.popleft()
if no not in visitados:
visitados.add(no)
fila.extend(grafo[no])
return visitados
Exercício 5: Por que usar deque em vez de lista para fila (BFS)?
→ deque.popleft() é O(1). list.pop(0) é O(n) — desloca todos os elementos.
Em BFS com n nós, usar lista seria O(n²) total. Com deque, O(n). Para filas, sempre use deque ou queue.Queue.
📝 Cola — Algoritmos e Programação
Big-O de Referência
| Operação | Complexidade |
|---|
| Acessar lista[i] / dict[k] | O(1) |
| Busca binária | O(log n) |
| Percorrer lista / busca linear | O(n) |
| Merge Sort / Quick Sort / sorted() | O(n log n) |
| Loop aninhado / Bubble Sort | O(n²) |
| Fibonacci ingênuo / subconjuntos | O(2ⁿ) |
Estrutura Certa para o Problema
| Precisa de... | Use | Por quê |
|---|
| Busca por chave | dict | O(1) médio |
| Unicidade / pertencimento | set | O(1) médio |
| Fila (FIFO) | deque | O(1) nas duas pontas |
| Pilha (LIFO) | list.append/pop | O(1) no fim |
| Menor/maior sempre disponível | heapq | O(log n) insert |
| Contar frequências | Counter | O(n) total |
⭐ Regras de Ouro
Regra
Constantes e termos menores somem: O(3n² + 5n + 2) =
O(n²)Regra
Loop simples = O(n). Loop dentro de loop =
O(n²)Regra
Dividir pela metade a cada passo =
O(log n)Regra
dict e set são
O(1) para busca — prefira a listas quando possível
Regra
Recursão sem memoização em Fibonacci =
O(2ⁿ). Com memo =
O(n)Regra
Use
deque para fila — list.pop(0) é O(n), deque.popleft() é O(1)