Cheat sheet de Big-O
Complexidade de tempo e espaço de cada estrutura de dados e algoritmo do BytePatterns, de tabelas hash a Dijkstra, cada linha com sua aula animada.
Atualizado em 78 linhas94 aulas vinculadasPronta para imprimir — use a impressão do seu navegador
Como ler
- n é o tamanho da entrada. Constantes e termos menores são descartados: 3n + 5 é O(n).
- O tempo é o do pior caso, a menos que a célula diga avg (médio) ou amortized (amortizado: barato, em média, ao longo de uma longa sequência de operações, mesmo que uma delas seja cara).
- Espaço é espaço extra — memória além da entrada, sem contar a saída. Recursão conta: a pilha de chamadas (call stack) dela é espaço.
- V e E são vértices e arestas; m e n são os dois tamanhos em um problema com duas strings ou com grid. Qualquer outra letra é definida na própria linha.
- Constante ou logarítmica
- Linear ou n log n
- Polinomial
- Exponencial ou fatorial
Nunca viu essa notação? O módulo de Big-O apresenta uma ideia de cada vez: O que é Big-O?, O(1) e O(n), O(log n) e a divisão pela metade, O(n²) e loops aninhados, Comparando complexidades.
Ordens de crescimento
O formato importa mais que os números: uma solução O(n²) que vai bem com n = 100 é inviável com n = 100.000. O gráfico mostra o formato para n pequeno; a tabela mostra a contagem de passos nos tamanhos que aparecem em restrições reais.
| Ordem | n = 10 | n = 1,000 | n = 1,000,000 |
|---|---|---|---|
| O(1) constante | 1 | 1 | 1 |
| O(log n) logarítmico | 3.3 | 10 | 19.9 |
| O(n) linear | 10 | 1,000 | 1,000,000 |
| O(n log n) linearítmico | 33.2 | 9,966 | ≈ 107 |
| O(n2) quadrático | 100 | 1,000,000 | ≈ 1012 |
| O(2n) exponencial | 1,024 | ≈ 10301 | ≈ 10301029 |
| O(n!) fatorial | 3,628,800 | ≈ 102567 | ≈ 105565708 |
| Limite da entrada | Geralmente cabe |
|---|---|
| n ≤ 10 | O(n!) |
| n ≤ 20 | O(2n) |
| n ≤ 500 | O(n3) |
| n ≤ 5.000 | O(n2) |
| n ≤ 106 | O(n log n) |
| n ≤ 107 | O(n) |
| maior | O(log n) ou O(1) |
Uma regra prática para um limite de um segundo, supondo cerca de 10⁷–10⁸ passos simples por segundo. Fatores constantes e a linguagem mudam isso; a ordem das linhas não muda.
Estruturas de dados
O custo de cada operação. O título de cada card leva à aula que a anima.
Array dinâmico
- Ler / escrever por índice
- O(1)
- Buscar (não ordenado)
- O(n)
- Adicionar ao final
- O(1) amortized
- Inserir / remover no meio
- O(n)
- Espaço
- O(n)
Todos os elementos depois da posição precisam ser deslocados.
Lista simplesmente encadeada
- Chegar ao k-ésimo nó
- O(n)
- Buscar
- O(n)
- Inserir / remover no head
- O(1)
- Inserir / remover após um nó conhecido
- O(1)
- Espaço
- O(n)
Veja também: Inserir e remover
Lista duplamente encadeada
- Inserir / remover em qualquer ponta
- O(1)
- Desligar um nó que você já tem
- O(1)
- Buscar
- O(n)
- Espaço
- O(n)
É o ponteiro prev que permite desligar um nó em O(1) — a base de um cache LRU.
Pilha
- Empilhar / desempilhar / peek
- O(1)
- Buscar
- O(n)
- Espaço
- O(n)
Fila / deque
- Enfileirar / desenfileirar
- O(1)
- Ver o início da fila
- O(1)
- Buscar
- O(n)
- Espaço
- O(n)
Remover do início de um array comum é O(n) — use um deque ou um buffer circular.
Veja também: Fila circular
Tabela hash (mapa / conjunto)
- Buscar
- O(1) avgO(n) worst
- Inserir
- O(1) avgO(n) worst
- Remover
- O(1) avgO(n) worst
- Espaço
- O(n)
O pior caso é ter todas as chaves em um só bucket. Não há ordem: percorrer em ordem custa O(n log n).
Veja também: Quando o hashing falha
Heap binário
- Ver o mínimo / máximo
- O(1)
- Inserir
- O(log n)
- Extrair o mínimo / máximo
- O(log n)
- Construir a partir de n itens (heapify)
- O(n)
- Buscar
- O(n)
- Espaço
- O(n)
Veja também: Heapify e sift · Fila de prioridade
Árvore binária de busca
- Buscar / inserir / remover
- O(h)
- …se balanceada
- O(log n)
- …se degenerada (uma cadeia)
- O(n)
- Percurso em ordem
- O(n)
- Espaço
- O(n)
h é a altura. Uma entrada ordenada gera a cadeia.
Veja também: Inserção e busca em BST · Profundidade e balanceamento da árvore
Trie
- Inserir uma palavra
- O(L)
- Buscar uma palavra
- O(L)
- Buscar por prefixo
- O(L)
- Espaço
- O(total characters)
L é o tamanho da palavra ou do prefixo — não depende de quantas palavras estão guardadas.
Veja também: Busca por prefixo · Trie ou hash set
Union-find (conjuntos disjuntos)
- Find / union, com as duas otimizações
- O(α(n)) amortized
- …só com união por tamanho
- O(log n)
- …sem nenhuma
- O(n)
- Espaço
- O(n)
α é a inversa da função de Ackermann: no máximo 4 para qualquer entrada que caiba na memória.
Veja também: Compressão de caminho · União por rank ou tamanho
Grafo — lista de adjacência
- Existe aresta u → v?
- O(deg u)
- Visitar todos os vizinhos de u
- O(deg u)
- Adicionar uma aresta
- O(1)
- Espaço
- O(V + E)
O padrão para grafos esparsos — ou seja, a maioria dos grafos de entrevista.
Veja também: O básico de grafos
Grafo — matriz de adjacência
- Existe aresta u → v?
- O(1)
- Visitar todos os vizinhos de u
- O(V)
- Adicionar uma aresta
- O(1)
- Espaço
- O(V2)
Só compensa quando o grafo é denso ou V é pequeno.
Ordenação
Ordenações por comparação não conseguem superar O(n log n) no pior caso; counting sort e radix sort contornam esse limite porque não comparam.
| Algoritmo | Melhor | Médio | Pior | Espaço | Estável | Observações |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n2) | O(n2) | O(1) | Sim | O melhor caso O(n) exige parar quando uma passada não faz nenhuma troca. |
| Selection sort | O(n2) | O(n2) | O(n2) | O(1) | Não | No máximo n − 1 trocas — sua única vantagem. |
| Insertion sort | O(n) | O(n2) | O(n2) | O(1) | Sim | Rápido em entradas quase ordenadas. |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Sim | |
| Quicksort | O(n log n) | O(n log n) | O(n2) | O(log n) | Não | O pior caso vem de pivôs ruins em sequência; a pilha então cresce até O(n). |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Não | |
| Counting sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Sim | k é o intervalo de valores. Só inteiros (ou chaves). |
| Radix sort | O(d·(n + b)) | O(d·(n + b)) | O(d·(n + b)) | O(n + b) | Sim | d dígitos na base b, uma passada estável por dígito. |
Busca
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Busca linear | O(n) | O(1) | |
| Busca binária | O(log n) | O(1) | Entrada ordenada. Versão iterativa; a recursiva soma O(log n) de pilha. |
| Busca em array ordenado e rotacionado | O(log n) | O(1) | Valores distintos. Duplicatas podem forçar O(n). |
| Encontrar um pico | O(log n) | O(1) | |
| Busca binária na resposta | O(Clog R) | O(1) | R é o tamanho do intervalo de respostas; C, o custo de uma verificação de viabilidade. |
| Busca em matriz 2D ordenada (escada) | O(m + n) | O(1) | m linhas, n colunas; cada passo descarta uma linha ou uma coluna. |
Técnicas com arrays, listas e strings
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Dois ponteiros | O(n) | O(1) | |
| Janela deslizante | O(n) | O(k) | Cada elemento entra e sai uma vez; k é o que a janela precisa lembrar. |
| Somas de prefixos | O(n) buildO(1) per query | O(n) | |
| Soma de subarray com hash map | O(n) | O(n) | |
| Subarray máximo de Kadane | O(n) | O(1) | |
| Product of array except self | O(n) | O(1) | Sem contar o array de saída. |
| Bandeira Holandesa (partição em três vias) | O(n) | O(1) | |
| Ponteiros rápido e lento (detecção de ciclo) | O(n) | O(1) | |
| Inverter uma lista encadeada | O(n) | O(1) | Versão iterativa. A recursão custa O(n) de pilha. |
| Pilha monotônica | O(n) amortized | O(n) | Cada elemento é empilhado uma vez e desempilhado no máximo uma vez. |
| Máximo da janela deslizante (deque) | O(n) | O(k) | |
| Busca de padrões com KMP | O(n + m) | O(m) | n é o texto; m, o padrão. |
| Rolling hash de Rabin–Karp | O(n + m) avgO(n·m) worst | O(1) | Pior caso quando o hash de toda janela colide. |
| Algoritmo Z | O(n + m) | O(n + m) |
Heaps e ordenação
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Top-k com um heap de tamanho k | O(n log k) | O(k) | |
| Top-k mais frequentes com buckets | O(n) | O(n) | |
| K-way merge | O(N log k) | O(k) | N itens no total, em k listas ordenadas. |
| Mediana contínua (dois heaps) | O(log n) addO(1) median | O(n) | |
| Mesclar intervalos | O(n log n) | O(n) | A ordenação domina; a varredura é O(n). |
| Meeting rooms (min-heap dos horários de término) | O(n log n) | O(n) |
Grafos e grids
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Busca em largura | O(V + E) | O(V) | |
| Busca em profundidade | O(V + E) | O(V) | Uma DFS recursiva pode estourar o limite da pilha em um caminho longo. |
| Menor caminho sem pesos (BFS) | O(V + E) | O(V) | |
| Flood fill em grid / ilhas | O(R·C) | O(R·C) | R linhas × C colunas: cada célula é visitada uma vez. |
| Ordenação topológica (Kahn) | O(V + E) | O(V) | |
| Dijkstra (heap binário) | O((V + E) log V) | O(V) | Só pesos não negativos. |
| Bellman–Ford | O(V·E) | O(V) | Aceita pesos negativos e detecta ciclos negativos. |
| Árvore geradora de Kruskal | O(E log E) | O(V) | Ordene as arestas e depois use union-find. |
| Árvore geradora de Prim (heap binário) | O(E log V) | O(V) | |
| Verificação de grafo bipartido (bicoloração) | O(V + E) | O(V) | |
| Componentes fortemente conexos | O(V + E) | O(V) |
Programação dinâmica
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Climbing stairs / estilo Fibonacci | O(n) | O(1) | Duas variáveis rotativas em vez da tabela. |
| House robber | O(n) | O(1) | |
| Coin change (menos moedas) | O(n·A) | O(A) | n tipos de moeda; A, o valor. |
| Mochila 0/1 | O(n·W) | O(W) | W é a capacidade; uma linha, preenchida da direita para a esquerda. |
| Maior subsequência comum | O(m·n) | O(m·n) | O(min(m, n)) de espaço se só o tamanho importar. |
| Distância de edição | O(m·n) | O(m·n) | |
| Maior subsequência crescente (DP) | O(n2) | O(n) | |
| Maior subsequência crescente (tails) | O(n log n) | O(n) | |
| Caminhos em um grid | O(m·n) | O(n) | Uma linha da tabela por vez. |
| DP de intervalos (cadeia de matrizes) | O(n3) | O(n2) |
Recursão e backtracking
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| Fibonacci recursivo ingênuo | O(2n) | O(n) | Um limite superior; o limite justo é cerca de 1,618ⁿ. |
| Recursão com memoização (Fibonacci) | O(n) | O(n) | |
| Todos os subconjuntos | O(n·2n) | O(n) | Sem contar a saída. |
| Todas as permutações | O(n·n!) | O(n) | Sem contar a saída. |
| N-queens | O(n!) | O(n) | Limite superior; a poda (pruning) corta a maior parte. |
Matemática e bits
| Algoritmo | Tempo | Espaço | Observações |
|---|---|---|---|
| MDC (Euclides) | O(log min(a, b)) | O(1) | |
| Exponenciação rápida | O(log n) | O(1) | Quadrados sucessivos, de forma iterativa; n é o expoente. |
| Crivo de Eratóstenes | O(n log log n) | O(n) | |
| XOR para achar o número único | O(n) | O(1) | |
| Contar bits ligados (zerando o 1 mais baixo) | O(k) | O(1) | k é o número de bits 1 — no máximo o tamanho da palavra. |
| Verificar potência de dois | O(1) | O(1) |
bytepatterns.com/cheatsheets/big-o — lá, cada linha leva a uma aula animada.