Pular para o conteúdo

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.

Como crescem as classes de complexidade mais comunsPassos em função do tamanho da entrada n, de 1 a 20, com corte em 60 passos. O(1) fica plano e O(log n) mal sobe; O(n) sobe de forma constante e O(n log n) um pouco mais rápido; O(n²) sai do gráfico antes de n chegar a 8, O(2ⁿ) antes de 6 e O(n!) antes de 5.15101520tamanho da entrada n →passos →O(n!)O(2n)O(n2)O(n log n)O(1)O(log n)O(n)
Passos em função de n, de n = 1 a 20, com corte em 60 passos.
Passos em tamanhos reais de entrada
Ordemn = 10n = 1,000n = 1,000,000
O(1) constante111
O(log n) logarítmico3.31019.9
O(n) linear101,0001,000,000
O(n log n) linearítmico33.29,966≈ 107
O(n2) quadrático1001,000,000≈ 1012
O(2n) exponencial1,024≈ 10301≈ 10301029
O(n!) fatorial3,628,800≈ 102567≈ 105565708
Da restrição à complexidade
Limite da entradaGeralmente cabe
n ≤ 10O(n!)
n ≤ 20O(2n)
n ≤ 500O(n3)
n ≤ 5.000O(n2)
n ≤ 106O(n log n)
n ≤ 107O(n)
maiorO(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.

Algoritmos de ordenação: tempo no melhor, médio e pior caso, espaço extra e estabilidade
AlgoritmoMelhorMédioPiorEspaçoEstávelObservações
Bubble sortO(n)O(n2)O(n2)O(1)SimO melhor caso O(n) exige parar quando uma passada não faz nenhuma troca.
Selection sortO(n2)O(n2)O(n2)O(1)NãoNo máximo n − 1 trocas — sua única vantagem.
Insertion sortO(n)O(n2)O(n2)O(1)SimRápido em entradas quase ordenadas.
Merge sortO(n log n)O(n log n)O(n log n)O(n)Sim
QuicksortO(n log n)O(n log n)O(n2)O(log n)NãoO pior caso vem de pivôs ruins em sequência; a pilha então cresce até O(n).
HeapsortO(n log n)O(n log n)O(n log n)O(1)Não
Counting sortO(n + k)O(n + k)O(n + k)O(n + k)Simk é o intervalo de valores. Só inteiros (ou chaves).
Radix sortO(d·(n + b))O(d·(n + b))O(d·(n + b))O(n + b)Simd dígitos na base b, uma passada estável por dígito.

Busca

Busca: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Busca em array ordenado e rotacionadoO(log n)O(1)Valores distintos. Duplicatas podem forçar O(n).
Encontrar um picoO(log n)O(1)
Busca binária na respostaO(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

Técnicas com arrays, listas e strings: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Dois ponteirosO(n)O(1)
Janela deslizanteO(n)O(k)Cada elemento entra e sai uma vez; k é o que a janela precisa lembrar.
Somas de prefixosO(n) buildO(1) per queryO(n)
Soma de subarray com hash mapO(n)O(n)
Subarray máximo de KadaneO(n)O(1)
Product of array except selfO(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 encadeadaO(n)O(1)Versão iterativa. A recursão custa O(n) de pilha.
Pilha monotônicaO(n) amortizedO(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 KMPO(n + m)O(m)n é o texto; m, o padrão.
Rolling hash de Rabin–KarpO(n + m) avgO(n·m) worstO(1)Pior caso quando o hash de toda janela colide.
Algoritmo ZO(n + m)O(n + m)

Heaps e ordenação

Heaps e ordenação: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Top-k com um heap de tamanho kO(n log k)O(k)
Top-k mais frequentes com bucketsO(n)O(n)
K-way mergeO(N log k)O(k)N itens no total, em k listas ordenadas.
Mediana contínua (dois heaps)O(log n) addO(1) medianO(n)
Mesclar intervalosO(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

Grafos e grids: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Menor caminho sem pesos (BFS)O(V + E)O(V)
Flood fill em grid / ilhasO(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–FordO(V·E)O(V)Aceita pesos negativos e detecta ciclos negativos.
Árvore geradora de KruskalO(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 conexosO(V + E)O(V)

Programação dinâmica

Programação dinâmica: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Climbing stairs / estilo FibonacciO(n)O(1)Duas variáveis rotativas em vez da tabela.
House robberO(n)O(1)
Coin change (menos moedas)O(n·A)O(A)n tipos de moeda; A, o valor.
Mochila 0/1O(n·W)O(W)W é a capacidade; uma linha, preenchida da direita para a esquerda.
Maior subsequência comumO(m·n)O(m·n)O(min(m, n)) de espaço se só o tamanho importar.
Distância de ediçãoO(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 gridO(m·n)O(n)Uma linha da tabela por vez.
DP de intervalos (cadeia de matrizes)O(n3)O(n2)

Recursão e backtracking

Recursão e backtracking: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
Fibonacci recursivo ingênuoO(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 subconjuntosO(n·2n)O(n)Sem contar a saída.
Todas as permutaçõesO(n·n!)O(n)Sem contar a saída.
N-queensO(n!)O(n)Limite superior; a poda (pruning) corta a maior parte.

Matemática e bits

Matemática e bits: tempo e espaço extra
AlgoritmoTempoEspaçoObservações
MDC (Euclides)O(log min(a, b))O(1)
Exponenciação rápidaO(log n)O(1)Quadrados sucessivos, de forma iterativa; n é o expoente.
Crivo de EratóstenesO(n log log n)O(n)
XOR para achar o número únicoO(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 doisO(1)O(1)

bytepatterns.com/cheatsheets/big-o — lá, cada linha leva a uma aula animada.