Você já escreveu um código que funcionava perfeitamente com 100 registros, mas travava miseravelmente com 100 mil? Se sim, você esbarrou em um dos conceitos mais importantes da ciência da computação: complexidade algorítmica.
Neste artigo, vou te mostrar como pensar sobre performance de verdade não aquela otimização prematura que a gente faz por paranoia, mas a análise que separa código amador de código profissional.
O Problema Real
Imagine que você precisa buscar um nome em uma lista de clientes. Com 10 clientes, qualquer abordagem funciona. Mas e com 10 milhões?
A diferença entre um algoritmo bem escolhido e um mal escolhido pode ser a diferença entre milissegundos e horas. Literalmente.
E é aí que entra a análise assintótica.
O Que É Análise Assintótica?
Análise assintótica é uma forma de descrever como o tempo de execução ou uso de memória de um algoritmo cresce conforme o tamanho da entrada aumenta.
A palavra “assintótica” vem de “assíntota” estamos interessados no comportamento quando os números ficam muito grandes. Não importa se seu algoritmo leva 5ms ou 50ms com 100 elementos. Importa o que acontece quando essa entrada escala para milhões.
Por Que Ignoramos Constantes?
Você vai ver que na notação Big O a gente ignora constantes e termos menores. Por exemplo, se um algoritmo faz 3n² + 5n + 100 operações, dizemos que ele é O(n²).
Parece estranho? Faz total sentido quando você pensa em escala:
| n | 3n² + 5n + 100 | n² |
|---|---|---|
| 10 | 450 | 100 |
| 1.000 | 3.005.100 | 1.000.000 |
| 1.000.000 | 3.000.005.000.100 | 1.000.000.000.000 |
Quando n cresce, o termo n² domina completamente. Os outros viram ruído estatístico.
Notação Big O: A Linguagem Universal de Performance
Big O é a notação que usamos para expressar essa complexidade. Pense nela como uma categoria de velocidade para algoritmos.
As Complexidades Mais Comuns (da melhor para a pior)
O(1) Tempo Constante
O santo graal. Não importa se você tem 10 ou 10 bilhões de elementos, o tempo é o mesmo.
// Acessar elemento por índice em um array
int valor = array[5];
// Buscar em um HashMap
String nome = mapa.get("chave");
O(log n) Tempo Logarítmico
Excelente. A cada operação, você elimina metade do problema. Busca binária é o exemplo clássico.
// Busca binária em array ordenado
// Com 1 bilhão de elementos: ~30 operações no máximo
int indice = Arrays.binarySearch(arrayOrdenado, valor);
O(n) Tempo Linear
Bom. Você precisa olhar cada elemento uma vez. É o melhor que dá pra fazer quando você precisa processar tudo.
// Somar todos os elementos
int soma = 0;
for (int num : array) {
soma += num;
}
O(n log n) Tempo Log-Linear
Muito bom. É a complexidade dos melhores algoritmos de ordenação genéricos (Merge Sort, Quick Sort).
// Ordenar um array
Arrays.sort(array);
O(n²) Tempo Quadrático
Problemático. Comum em loops aninhados. Funciona para entradas pequenas, mas escala mal.
// Encontrar duplicatas (abordagem ingênua)
for (int i = 0; i < array.length; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] == array[j]) {
// encontrou duplicata
}
}
}
O(2ⁿ) Tempo Exponencial
Desastroso. Cada elemento adicional dobra o tempo. Comum em algoritmos de força bruta para problemas combinatórios.
// Fibonacci recursivo ingênuo (não faça isso)
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
}
Visualizando a Diferença
Para entender o impacto real, olha essa tabela com n = 1.000.000:
| Complexidade | Operações | Se cada operação = 1μs |
|---|---|---|
| O(1) | 1 | 1 microsegundo |
| O(log n) | 20 | 20 microsegundos |
| O(n) | 1.000.000 | 1 segundo |
| O(n log n) | 20.000.000 | 20 segundos |
| O(n²) | 1.000.000.000.000 | 11,5 dias |
| O(2ⁿ) | … | mais que a idade do universo |
Agora você entende por que a escolha importa.
Estruturas de Dados e Suas Complexidades
Cada estrutura de dados tem trade-offs. Não existe bala de prata — existe a ferramenta certa para cada problema.
Array / ArrayList
O array é a estrutura mais fundamental. Elementos contíguos na memória.
| Operação | Complexidade |
|---|---|
| Acesso por índice | O(1) |
| Busca (não ordenado) | O(n) |
| Inserção no final | O(1) amortizado |
| Inserção no meio | O(n) |
| Remoção no meio | O(n) |
Quando usar: Quando você precisa de acesso rápido por índice e o tamanho é relativamente estável.
LinkedList
Elementos espalhados na memória, conectados por ponteiros.
| Operação | Complexidade |
|---|---|
| Acesso por índice | O(n) |
| Busca | O(n) |
| Inserção no início/fim | O(1) |
| Inserção no meio (com referência) | O(1) |
| Remoção (com referência) | O(1) |
Quando usar: Quase nunca. Sério. A vantagem teórica raramente compensa a perda de cache locality. ArrayList ganha na prática em 99% dos casos.
HashMap / HashTable
A estrutura que todo dev deveria dominar. Usa uma função hash para mapear chaves a posições.
| Operação | Caso Médio | Pior Caso |
|---|---|---|
| Inserção | O(1) | O(n) |
| Busca | O(1) | O(n) |
| Remoção | O(1) | O(n) |
O pior caso acontece quando muitas chaves colidem no mesmo bucket. Com uma boa função hash e fator de carga adequado, isso é raro.
Quando usar: Sempre que precisar de busca rápida por chave. É a estrutura mais versátil que existe.
TreeMap / Árvore Binária de Busca Balanceada
Mantém elementos ordenados usando uma estrutura de árvore.
| Operação | Complexidade |
|---|---|
| Inserção | O(log n) |
| Busca | O(log n) |
| Remoção | O(log n) |
| Menor/Maior elemento | O(log n) |
| Percorrer em ordem | O(n) |
Quando usar: Quando você precisa dos dados ordenados ou precisa de operações como “todos os elementos entre X e Y”.
HashSet / TreeSet
São como HashMap/TreeMap, mas armazenam apenas chaves (sem valores).
Quando usar: Para verificar existência ou eliminar duplicatas.
// Verificar duplicatas em O(n) ao invés de O(n²)
Set<Integer> vistos = new HashSet<>();
for (int num : array) {
if (!vistos.add(num)) {
// num é duplicata
}
}
Stack (Pilha) e Queue (Fila)
Estruturas com regras específicas de acesso.
Stack (LIFO): último a entrar, primeiro a sair Queue (FIFO): primeiro a entrar, primeiro a sair
| Operação | Complexidade |
|---|---|
| Push/Enqueue | O(1) |
| Pop/Dequeue | O(1) |
| Peek | O(1) |
Quando usar: Quando a ordem de processamento importa. Stack para recursão/backtracking, Queue para BFS e processamento em ordem de chegada.
Heap / Priority Queue
Árvore binária onde o pai é sempre maior (max-heap) ou menor (min-heap) que os filhos.
| Operação | Complexidade |
|---|---|
| Inserção | O(log n) |
| Remover maior/menor | O(log n) |
| Consultar maior/menor | O(1) |
Quando usar: Quando você precisa repetidamente do maior ou menor elemento. Exemplos: algoritmo de Dijkstra, mediana de stream, top-K elementos.
Complexidade de Espaço: A Memória Também Conta
Não é só tempo que importa. Memória também tem complexidade.
// O(1) de espaço - variáveis fixas
int soma = 0;
for (int num : array) soma += num;
// O(n) de espaço - cria novo array do mesmo tamanho
int[] copia = array.clone();
// O(n²) de espaço - matriz n x n
int[][] matriz = new int[n][n];
Trade-offs entre tempo e espaço são comuns. Memoização, por exemplo, troca memória por velocidade.
Análise Amortizada: A Média Que Importa
Algumas operações são “caras” ocasionalmente, mas baratas na média.
O ArrayList é o exemplo perfeito. Quando o array interno enche, ele precisa criar um novo array maior e copiar tudo — operação O(n). Mas isso acontece raramente.
Se o array dobra de tamanho quando enche, a média de todas as inserções ainda é O(1). Isso é análise amortizada.
ArrayList<Integer> lista = new ArrayList<>();
// Cada add() é O(1) amortizado
for (int i = 0; i < 1000000; i++) {
lista.add(i);
}
Casos Práticos: Aplicando o Conhecimento
Caso 1: Encontrar Dois Números que Somam um Alvo
Abordagem ingênua O(n²):
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
Abordagem otimizada O(n):
Map<Integer, Integer> mapa = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complemento = target - nums[i];
if (mapa.containsKey(complemento)) {
return new int[]{mapa.get(complemento), i};
}
mapa.put(nums[i], i);
}
A segunda abordagem usa O(n) de espaço extra, mas reduz o tempo dramaticamente.
Caso 2: Verificar Anagramas
Abordagem ingênua O(n log n):
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
return Arrays.equals(arr1, arr2);
Abordagem otimizada O(n):
int[] contagem = new int[26];
for (char c : s1.toCharArray()) contagem[c - 'a']++;
for (char c : s2.toCharArray()) contagem[c - 'a']--;
for (int c : contagem) if (c != 0) return false;
return true;
Caso 3: Top K Elementos Mais Frequentes
Abordagem ingênua O(n log n): Ordenar por frequência e pegar os K primeiros.
Abordagem otimizada O(n log k): Usar um min-heap de tamanho K. Para cada elemento, adicione ao heap. Se o heap passar de K elementos, remova o menor. No final, o heap contém os K maiores.
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.merge(num, 1, Integer::sum);
}
PriorityQueue<Integer> heap = new PriorityQueue<>(
Comparator.comparingInt(freq::get)
);
for (int num : freq.keySet()) {
heap.offer(num);
if (heap.size() > k) heap.poll();
}
Dicas Para o Dia a Dia
- Conheça suas estruturas: HashMap é seu melhor amigo para a maioria dos problemas de busca.
- Desconfie de loops aninhados: Dois loops aninhados sobre a mesma coleção geralmente significam O(n²). Pergunte-se se há uma forma melhor.
- Ordenação é poderosa: Muitos problemas O(n²) viram O(n log n) se você ordenar primeiro.
- Meça antes de otimizar: Big O te dá a teoria, mas profilers te dão a realidade. Às vezes O(n²) com constantes pequenas bate O(n log n) com constantes grandes para entradas pequenas.
- Pense em trade-offs: Frequentemente você pode trocar espaço por tempo (memoização, caching, pré-computação).
Conclusão
Entender complexidade algorítmica não é sobre decorar tabelas. É sobre desenvolver uma intuição para reconhecer padrões e escolher a ferramenta certa.
Quando você olha um problema e imediatamente pensa “isso parece O(n²), mas se eu usar um HashSet consigo O(n)”, você está pensando como um engenheiro de software sênior.
A diferença entre código que funciona e código que escala está aqui.
Gostou do conteúdo? Compartilha com aquele colega que ainda usa dois loops for onde caberia um HashMap.
