Projeto Final: Comparando Implementações

Você passou por 12 nós: de "por que medir" até "quando Big O mente". Agora é hora de medir de verdade e ver a diferença na pele, não só no papel.

O objetivo: pegar 3 problemas clássicos, implementar 2 soluções cada (de complexidades diferentes) e medir quanto cada uma demora. Você vai ver que, na prática, os números confirmam (ou surpreendem) o que a teoria prometeu.

Os 3 problemas

Problema 1 - encontrar par que soma X

Lista ordenada, par de números que somam X.

• Solução A (O(n²)): loop duplo - testa todos os pares.
• Solução B (O(n)): dois ponteiros - um de cada lado.

Problema 2 - tem item duplicado

Lista não ordenada, retornar True se algum item aparece 2+ vezes.

• Solução A (O(n²)): loop duplo comparando tudo.
• Solução B (O(n)): hash set - guarda o que já viu e checa em O(1).

Problema 3 - contar frequência de palavras

Texto com N palavras, contar quantas vezes cada uma aparece.

• Solução A (O(n²)): lista de pares (palavra, count) com busca linear.
• Solução B (O(n)): hash map.

O que medir

Para cada par de soluções, meça o tempo em 3 tamanhos de entrada: pequeno (n=100), médio (n=10.000), grande (n=1.000.000).

Você vai ver algo assim:

Problema 2 (tem duplicata), Solução A (O(n²)):
  n=100:        0.0001s
  n=10.000:     0.08s
  n=1.000.000:  8.5s           # aqui já fica visível a dor

Problema 2 (tem duplicata), Solução B (O(n)):
  n=100:        0.00005s
  n=10.000:     0.005s
  n=1.000.000:  0.5s           # mesma operação, 17× mais rápido

Repare como O(n²) vs O(n) parece "5x" para n=100 (constante importa) e vira 17x para n=1.000.000 (a complexidade vence).

Como medir

Em Python:

import time

def medir(fn, *args):
    t0 = time.perf_counter()
    fn(*args)
    return time.perf_counter() - t0

print(medir(solucao_a, lista_grande))   # 8.5
print(medir(solucao_b, lista_grande))   # 0.5

Em JavaScript/Node:

function medir(fn, ...args) {
  const t0 = performance.now();
  fn(...args);
  return performance.now() - t0;
}

Dica: rode cada medição várias vezes e tire a média. A primeira execução pode ser afetada por cache, JIT, etc.

O que anotar

Faça uma tabela no seu caderno (ou num .md) com:

Critério de "pronto"

1. As 6 implementações (2 por problema) estão escritas e funcionam.
2. As medições estão em uma tabela, em todos os 3 tamanhos.
3. Você consegue explicar por que os números saíram como saíram.
4. Opcional: poste no LinkedIn / Twitter com a tabela. Mostrar "olha a diferença real entre O(n) e O(n²)" é didático e viraliza.

🎉 Você terminou a trilha de Complexidade de Algoritmos. Você sabe contar operações, ler Big O, identificar o padrão certo para o problema, e - mais importante - medir antes de otimizar. Esse é o kit de sobrevivência de quem escreve código que aguenta o tranco quando o volume sobe. Próximos passos: escolha Estruturas de Dados (se ainda não viu) ou vá direto para uma trilha de Backend/DevOps e aplique tudo isso em sistemas maiores.