Projeto Final: Comparando Implementações de Verdade

Você passou por 13 nós: de "auto-diagnóstico" até "tries". Agora é hora de medir de verdade e ver a diferença na pele, não só no papel. A pergunta que essa trilha inteira tentou responder é: "escolher a estrutura certa muda o resultado?". Spoiler: muda.

O objetivo

Pegar 3 problemas clássicos, implementar 2 soluções cada (de complexidades diferentes), medir o tempo em 3 tamanhos de entrada e comparar na tabela. 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 de números, encontrar par de elementos cuja soma é X. Retorna os índices do par (ou null se não houver).

• Solução A (O(n²)): loop duplo - testa todos os pares.
• Solução B (O(n)): dois ponteiros - um do início, um do fim, ajusta conforme a soma for maior ou menor que X.

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 todos os pares.
• 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. Retorna um Map/dict {palavra: count}.

• Solução A (O(n²)): lista de pares (palavra, count) com busca linear pra incrementar.
• 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 JavaScript/Node:

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

Em Python:

import time

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

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

O que anotar

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

Desafios extras (opcional, pra quem quer ir além)

Quer ir além do projeto mínimo? Tente estes:

• Adicione BST ao Problema 1 (lista não ordenada): insira todos em BST, depois pra cada elemento faça busca do complemento (X - elemento) em O(log n). Total: O(n log n). Compare com as soluções O(n²) e O(n).
• Implemente union-find e use no Problema 2: agrupa elementos já vistos, e checa se o novo elemento está no mesmo grupo. Curiosidade, não muda a complexidade (O(n) amortizado).
• Use um heap pra achar o k-ésimo menor elemento: Problema 4
  • dado lista e k, retornar o k-ésimo menor. Heap de máximo de tamanho k dá O(n log k). Compare com sort completo (O(n log n)).

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.

Onde você está agora

Você passou por 13 nós cobrindo as estruturas mais importantes em código de produção: sequências (array, lista), pilhas, filas, hash tables, recursão com árvores, árvores (BST, balanceadas), heaps, grafos (representação, BFS/DFS, algoritmos clássicos) e tries. Você sabe:

• Por que array vence lista ligada em quase todo caso (cache locality).
• Por que hash table é tão rápido (função hash + array, com redimensionamento amortizado).
• Por que BST desbalanceada é perigosa e AVL/Red-Black existem.
• Por que heap é a estrutura por trás de toda fila de prioridade.
• Por que grafo aparece em todo sistema "real" e BFS/DFS/ Dijkstra são os algoritmos base.
• Por que trie é a estrutura pra busca por prefixo e matching de padrões.

Próximos passos recomendados:

• Complexidade de Algoritmos
  • se você pulou essa trilha, agora é hora. Aprofunda a análise de Big O, padrões clássicos (dois ponteiros, sliding window, divide and conquer) e a base teórica.
• Algoritmos de string (KMP, Z-alg, suffix array, Aho-Corasick)
  • trilha futura. Aprofunda o que vimos em tries.
• Estruturas concorrentes (lock-free queue, concurrent hash map) - trilha futura. Quando o sistema tem múltiplas threads, as estruturas "normais" não bastam.
• Banco de dados teoria (B-tree, índice hash, MVCC) - as estruturas desta trilha aparecem no coração de qualquer banco.

🎉 Você terminou a trilha de Estruturas de Dados. Você sabe escolher entre array, hash, árvore e grafo com base no problema, entender o que está por baixo das estruturas que sua linguagem oferece, 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 uma trilha de backend/devops e aplique tudo isso em sistemas maiores, ou aprofunde em uma estrutura específica (grafos, árvores balanceadas, estruturas concorrentes).