Complexidade de tempo e complexidade de espaço de um algoritmo explicadas.
Imagine dois programas que fazem exatamente a mesma coisa. Alimente cada um com mil registros e você não conseguirá diferenciá-los. Mas alimente-os com um bilhão, e um terminará antes mesmo de você soltar a tecla Enter, enquanto o outro ainda estará trabalhando até a próxima terça-feira.
Mesmo laptop. Mesmos dados. O que os diferencia é a complexidade de tempo, que nada mais é do que um nome para a rapidez com que a carga de trabalho de um algoritmo aumenta à medida que você fornece mais dados de entrada.
Vamos analisar o significado do termo, como a notação Big O o representa, como deduzi-lo a partir de um código real e onde entra a complexidade de espaço. Por fim, chegaremos a um ponto em que tudo isso deixa de ser tarefa de casa e começa a custar dinheiro de verdade: os contratos inteligentes.
O que é a complexidade de tempo de um algoritmo?
Esqueça os segundos por um momento. A complexidade de tempo conta os passos. Comparações, atribuições, um pouco de aritmética aqui e ali, e você escreve o total como uma função de n, que é o tamanho da entrada.
Eis aqui a função mais entediante que se possa imaginar:
python def print_all(items): for item in items: print(item)
Dez itens? Dez viagens pelo circuito. Dez mil? Dez mil viagens.
O trabalho aumenta em linha reta ao lado da entrada, por isso o chamamos de O(n).
Agora, talvez cada viagem custe três pequenas operações em vez de uma. Tudo bem, isso dá 3n. Honestamente, ninguém se importa, porque dobrar a lista ainda dobra o trabalho, e essa curva de crescimento é o que nos interessa. O número exato é omitido de propósito.
É por isso que todos os cursos de Estruturas de Dados e Algoritmos e metade das entrevistas de emprego para programadores enfatizam a complexidade de tempo. Se você consegue inferir a complexidade de um algoritmo apenas olhando para ele, pode prever como ele se comportará com dados de entrada que você nunca teve tempo de testar. O que, em produção, representa a maior parte dos dados.
Por que o tempo de execução é uma medida inadequada de um algoritmo
Então, por que não simplesmente executar o processo com um temporizador? Muita gente faz isso, e eu entendo. O problema é que o tempo de execução traz consigo uma série de coisas com as quais seu algoritmo não tem nada a ver:
- Hardware. Meu laptop de cinco anos e um servidor na nuvem novinho em folha apresentarão resultados completamente diferentes para o mesmo script.
- Linguagem de programação. Escreva o mesmo loop em C e em Python e você poderá observar uma diferença de desempenho de 10 vezes, ou até mais.
- Carga do sistema. Algum atualizador em segundo plano entra em ação, o coletor de lixo é ativado, o cache fica frio. Seu resultado é movido.
- Qualquer que seja a entrada que você tenha recebido. Uma ordenação que funciona muito bem com dados quase ordenados pode ser extremamente lenta com dados embaralhados.
Um cronômetro registra uma única medição em um dispositivo com uma única entrada. Multiplique esses dados por 100 e ele não terá nenhuma informação.
A contagem de passos não oscila. Mesmo algoritmo, mesma entrada, e você obtém o mesmo número de passos, seja em Rust num servidor rack ou em JavaScript no celular de alguém. É por isso que a complexidade de tempo é uma comparação justa entre duas soluções antes mesmo de se realizar um benchmark. Eu ainda faria um benchmark depois, se isso fosse relevante. É apenas uma questão diferente.
Explicação da notação Big O e outras notações assintóticas
Os livros didáticos chamam isso de notação assintótica, que soa pior do que realmente é. Você deixa n crescer enormemente e para de se importar com os detalhes menores, então multiplicadores constantes e entradas minúsculas desaparecem e apenas a curva de crescimento permanece. Existem três delas que vale a pena conhecer:
| Notação | O que descreve | Significado literal | Exemplo |
|---|---|---|---|
| O grande, O(f(n)) | Limite superior | O algoritmo não cresce mais rápido que f(n) | A busca linear é O(n) |
| Ômega Grande, Ω(f(n)) | Limite inferior | O algoritmo precisa de pelo menos f(n) trabalhos. | Qualquer ordenação por comparação é Ω(n log n) |
| Big-Theta, Θ(f(n)) | Amarrado firmemente | Os limites superior e inferior coincidem. | O merge sort é Θ(n log n) |
Na prática, você ouvirá a notação Big O em cerca de 95% dos casos. Ela define um limite superior, o que significa que o tempo de execução não crescerá mais rápido do que a taxa dentro dos parênteses. Na minha primeira revisão de código em um emprego de verdade, um desenvolvedor sênior escreveu "O(n²), por favor, corrija" ao lado de um loop aninhado, e o que ele queria dizer era que a complexidade de tempo no pior caso era quadrática e a lista estava prestes a ficar muito maior.
Omega e Theta são termos usados principalmente em cursos universitários sobre análise de algoritmos, e acho que não uso nenhum dos dois no trabalho há anos. Big O leva a melhor porque responde à pergunta que as pessoas realmente fazem em reuniões: "quão ruim fica se o tráfego triplicar?"
Há um detalhe técnico que me confundiu por um tempo. Já que a notação Big O é apenas um limite máximo, uma função O(n) também é O(n²), estritamente falando, da mesma forma que uma pessoa de 1,5 metro tem "menos de 2,1 metros". Verdade, mas inútil. Todo mundo cita o limite mais preciso que consegue justificar, e eu farei o mesmo.
Classes comuns de complexidade de tempo com exemplos
Não há muitas classes que você verá em código real, talvez sete se você contar as mais complexas. Este é aproximadamente o custo de cada uma com n = 1.000:
| Aula | Nome | Exemplo típico | Operações em n = 1.000 |
|---|---|---|---|
| O(1) | Constante | Índice de matriz, pesquisa em tabela hash | 1 |
| O(log n) | Logarítmico | Busca binária | ~10 |
| Sobre) | Linear | Analisando uma lista | 1.000 |
| O(n log n) | Linearítmico | Classificação por intercalação, classificação rápida (média) | ~10.000 |
| O(n²) | Quadrático | Laços aninhados, ordenação por bolha | 1.000.000 |
| O(2ⁿ) | Exponencial | Fibonacci recursivo ingênuo | Mais do que átomos no universo |
| Sobre!) | Fatorial | vendedor viajante de força bruta | Ainda maior |
O(1): Tempo constante
Quer o seu dicionário Python tenha dez chaves ou dez milhões, extrair uma chave por vez custa praticamente o mesmo, assim como ler itens[5] de uma lista. Essa linearidade é a essência do tempo constante.
O(log n): Tempo Logarítmico
Penso nesses algoritmos como "adivinhe o número entre 1 e 100", onde cada tentativa elimina metade das possibilidades restantes. A busca binária faz exatamente isso em uma lista ordenada:
python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Com um bilhão de itens classificados, são necessárias cerca de 30 comparações, enquanto analisá-los um por um poderia levar o bilhão inteiro, e eu nunca deixei de achar isso engraçado.
O(n) e O(n log n)
Um algoritmo linear visita cada elemento um número fixo de vezes, da mesma forma que você faria se estivesse procurando o maior número em uma coluna de planilha a olho nu. A complexidade O(n log n) é ideal para uma ordenação eficiente. O algoritmo de ordenação por intercalação (merge sort) divide a lista em itens individuais (log n níveis de divisão) e então realiza uma passagem linear por nível durante a intercalação, de modo que seu tempo de execução permanece o mesmo, independentemente de os dados chegarem ordenados ou embaralhados.
O(n²) e pior
O código quadrático quase sempre tem um laço dentro de outro laço, como esta verificação de duplicados que compara cada par:
python def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False
O crescimento exponencial e fatorial são muito piores. O Fibonacci recursivo clássico continua resolvendo os mesmos subproblemas repetidamente, então cada aumento de 1 em n praticamente dobra o trabalho. Com n = 20, você não notará diferença; com n = 60, você pode ir preparar o jantar, comê-lo, lavar a louça e ainda assim não terá terminado.
Como calcular a complexidade de tempo passo a passo
Quase nunca é necessário uma prova formal para calcular a complexidade de tempo. Eu reviso esta lista mentalmente e ela abrange a maior parte do código que vejo:
- Defina n. Decida qual é o tamanho da entrada: o comprimento de uma lista, o número de nós em um grafo, o número de dígitos em um número.
- Conte o trabalho em cada linha. Instruções simples (atribuições, comparações, aritmética) custam O(1).
- Adicione blocos sequenciais. Dois loops um após o outro, cada um sobre n, resultam em n + n = 2n.
- Multiplicação de blocos aninhados. Um laço sobre n dentro de outro laço sobre n resulta em n × n = n².
- Elimine as constantes. 2n torna-se n, e 500 torna-se 1.
- Mantenha apenas o termo dominante. Em n² + n, a parte n² torna-se muito maior que o restante à medida que n cresce.
Resolvi rapidinho. Sua contagem resulta em T(n) = 3n² + 5n + 2. Insira um milhão: 3n² é três trilhões, 5n é cinco milhões. Erro de arredondamento. Digamos que seja O(n²), pronto.
Os loops que pulam em vez de passar por um são mais sorrateiros:
python def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
A cada iteração, n é reduzido pela metade, então este loop while desiste após aproximadamente log₂(n) iterações. Essa é basicamente a resposta para a pergunta "quando a complexidade de tempo é O(log n)?". Se o que resta diminui por um fator constante a cada passo, então você chegou lá.
A recursão precisa de mais uma ferramenta, uma recorrência. O merge sort realiza duas tarefas com metade do tamanho e depois uma mesclagem, então T(n) = 2T(n/2) + n. O teorema mestre é uma espécie de guia para recorrências desse tipo, e para esta em particular, ele resulta em O(n log n).
Uma regra prática da programação competitiva que eu uso bastante: uma máquina normal executa algo como 10⁸ operações simples por segundo. É um valor bem aproximado, mas suficiente para verificar a complexidade de tempo de uma solução antes de enviá-la. Com n em 10⁵, O(n²) corresponde a cerca de 10¹⁰ operações, então o tempo limite é atingido. O(n log n) é menos de 2 milhões. Passa sem problemas.
Análise do pior cenário, do melhor cenário e do cenário médio
Ao alimentar o mesmo algoritmo com entradas diferentes, a quantidade de trabalho pode variar drasticamente. A busca linear ilustra isso muito bem:
- Na melhor das hipóteses: o que você quer está bem na frente. Uma comparação e você está fora.
- Na pior das hipóteses: está no final, ou não está lá de todo. Isso são n comparações.
- Caso médio: se pudesse estar em qualquer lugar com probabilidades iguais, você verificará em média n/2. Ainda assim, O(n), observe.
Pergunte a um desenvolvedor sobre "a complexidade" de algo e ele quase sempre lhe dará a complexidade de tempo no pior caso, porque esse número é uma garantia que você pode levar em consideração no planejamento.
Suponha que sua API processe uma requisição em O(n) na pior das hipóteses. Ótimo, agora você sabe como a requisição mais lenta se comporta e também está protegido caso alguém envie dados inválidos de propósito. Isso é algo que as pessoas fazem com frequência: se um atacante descobrir quais chaves causam colisões na sua tabela hash, essas serão as únicas chaves que você verá por um bom tempo.
Vale a pena analisar o caso médio, já que o cenário ruim raramente ocorre. O Quicksort é o exemplo perfeito disso, com complexidade média de O(n log n), mas que pode chegar a O(n²) se você escolher pivôs de forma ingênua em dados já ordenados. As bibliotecas padrão contornam esse problema com pivôs aleatórios ou trocando para um algoritmo de ordenação diferente quando a recursão se torna suspeitamente profunda.
O que são complexidade espacial e espaço auxiliar?
A memória é a outra despesa que um algoritmo acarreta. A complexidade de espaço rastreia quanta memória é necessária à medida que o tamanho da entrada aumenta, e você a representa com a mesma notação Big O usada para o tempo.
Parte dessa memória é a própria entrada, pela qual você paga independentemente do que faça com ela. A parte que você realmente controla é chamada de espaço auxiliar, ou seja, os recursos extras que seu código aloca enquanto está em execução, como variáveis temporárias e novos arrays, além da pilha de chamadas que ninguém lembra até que cause problemas.
Alguns exemplos rápidos:
- Trocar duas variáveis requer alguns espaços, independentemente de qualquer outra coisa, então é espaço auxiliar O(1).
- Copiar uma lista de n itens para uma nova lista custa O(n) de memória adicional.
- Ao recursar n níveis de profundidade, n quadros permanecem na pilha, o que ocupa espaço O(n), mesmo que você nunca tenha construído um array.
Vi um desenvolvedor júnior perder uma tarde inteira por causa disso. A função recursiva dele parecia não usar memória nenhuma, mas cada chamada incompleta ficava parada na pilha, esperando as chamadas mais profundas retornarem, e com uma entrada grande, tudo travava com um estouro de pilha.
Muitas otimizações consistem em trocar memória por tempo ou vice-versa. A memoização armazena em cache os resultados já calculados, o que reduz a complexidade do cálculo de Fibonacci de O(2ⁿ) para O(n) em troca de memória O(n). Tabelas hash permitem buscas com complexidade média O(1) ao alocar espaço em buckets. Em um servidor com 64 GB de RAM, essa troca geralmente é óbvia, mas em um microcontrolador ou dentro de um contrato inteligente, seria preciso pensar duas vezes.
Complexidade de tempo e espaço de estruturas de dados comuns
Escolher a estrutura de dados correta geralmente é mais vantajoso do que ficar ajustando minuciosamente qualquer coisa dentro do seu loop. Custos médios para as estruturas que você mais usará:
| Estrutura de dados | Acesso | Procurar | Inserir | Excluir | Espaço |
|---|---|---|---|---|---|
| Variedade | O(1) | Sobre) | Sobre) | Sobre) | Sobre) |
| Lista encadeada | Sobre) | Sobre) | O(1) | O(1) | Sobre) |
| Tabela hash | n / D | O(1) | O(1) | O(1) | Sobre) |
| Árvore de busca binária balanceada | O(log n) | O(log n) | O(log n) | O(log n) | Sobre) |
| Heap binário | O(1) para min/max | Sobre) | O(log n) | O(log n) | Sobre) |
Duas observações. As inserções e remoções em listas encadeadas são apenas O(1) se você já estiver segurando o nó. E uma tabela hash pode chegar a O(n) quando muitas chaves colidem.
Os algoritmos de ordenação variam bastante:
| Algoritmo de ordenação | Melhor | Média | Pior | Espaço auxiliar |
|---|---|---|---|---|
| Classificação de bolhas | Sobre) | O(n²) | O(n²) | O(1) |
| Classificação por intercalação | O(n log n) | O(n log n) | O(n log n) | Sobre) |
| Classificação rápida | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Ordenação por heap | O(n log n) | O(n log n) | O(n log n) | O(1) |
O merge sort é previsível, mas exige mais memória. O heap sort ordena no próprio local e mantém o mesmo pior caso. O quicksort, apesar do teto mais problemático, tende a ser o mais eficaz na prática.
Complexidade Temporal em Blockchain e Contratos Inteligentes
É aqui que a coisa fica interessante. No seu próprio servidor, um algoritmo malfeito desperdiça CPU e talvez irrite um usuário. No Ethereum ou em qualquer blockchain EVM, ele desperdiça dinheiro. Cada opcode executado por um contrato inteligente custa gás, pago na moeda nativa da blockchain, então a sua contagem de operações aparece como uma linha na fatura de alguém. Em outras palavras, uma complexidade de tempo ruim tem um preço.
Imagine que você tem um contrato que percorre todos os detentores de tokens para pagar recompensas. O custo computacional é O(n), e o gás aumenta gradativamente a cada novo detentor. No dia do lançamento, ninguém percebe.
Então a lista de detentores continua crescendo. Um dia, o pagamento precisa de mais gás do que o limite de gás do bloco, que é o limite máximo de gás que um único bloco pode conter. Depois disso, a transação não pode ser concluída. Não é que "esteja lenta". Simplesmente nunca é concluída, e quaisquer fundos que estivessem aguardando por trás dessa função ficam basicamente presos. Os auditores registram loops ilimitados como esse como ataques de negação de serviço, e com razão.
As soluções se resumem ao pensamento complexo, pura e simplesmente:
- Divida o trabalho em lotes de tamanho fixo ao longo de várias transações.
- Inverta a lógica para que cada usuário reivindique sua própria recompensa. Cada chamada é O(1).
- Troque o loop por uma prova Merkle.
Adoro as provas de Merkle como exemplo de por que o logaritmo de n é tão importante na blockchain. Uma árvore de Merkle transforma uma grande quantidade de dados em um único hash raiz.
Para provar que uma entrada pertence a um conjunto de n, você precisa de aproximadamente log₂(n) hashes. Para um milhão de entradas, isso dá cerca de 20. Não um milhão. Os airdrops se baseiam nisso, e carteiras Bitcoin leves usam o mesmo truque para confirmar uma transação sem baixar o bloco inteiro.
Fora da blockchain, a situação é a mesma. Imagine um sistema de pagamentos que associa cada transação recebida na blockchain a uma fatura, analisando todas as faturas em aberto. A complexidade é O(n) por pagamento, e fica mais lenta à medida que a loja cresce. Coloque as faturas em um mapa hash indexado por endereço ou ID e cada correspondência terá complexidade O(1). E se você preferir não construir e gerenciar toda essa infraestrutura, um gateway de pagamento em criptomoedas como o Plisio faz isso para você.
