Explorador de complexidade Big-O

Veja como as classes de complexidade dos algoritmos crescem à medida que o tamanho da entrada N aumenta.

Exemplo resolvido — Explorador de complexidade Big-O

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10.000

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Explorador de complexidade Big-O

O Big-O é um limite superior para o crescimento, não uma medição de tempo. Dizer que um algoritmo é O(N²) afirma que, a partir de determinado tamanho de entrada, o seu trabalho se mantém abaixo de um múltiplo fixo de N² — não diz nada sobre segundos, e absolutamente nada sobre entradas pequenas.

O que significa cada símbolo

N: o tamanho da entrada — quantos elementos são entregues ao algoritmo. É o número definido acima, em qualquer valor de 2 a 1 000 000.
f(N): o trabalho efetivamente realizado para esse tamanho, contado em operações abstratas em vez de segundos.
c: um multiplicador constante que a notação tem permissão para ocultar. A afirmação é f(N) ≤ c·g(N); c pode ser 2 ou 2000, e é precisamente essa a informação que o Big-O descarta.
n₀: o tamanho a partir do qual o limite tem de se verificar. Abaixo de n₀, as classes podem surgir em qualquer ordem, razão pela qual os cinco números acima se agrupam para valores pequenos de N.

De onde vem a fórmula

Parta da afirmação que se pretende tornar precisa: o trabalho f(N) acaba por não crescer mais depressa do que uma função de referência g(N).
“Não mais depressa” tem de tolerar um fator constante, porque otimizar um ciclo interno altera a constante e não a forma. Assim, permita um multiplicador: f(N) ≤ c·g(N).
E “acaba por” tem de tolerar entradas pequenas, onde tudo pode acontecer. Exija a desigualdade apenas quando N ≥ n₀. Em conjunto: f(N) = O(g(N)) significa que existem um c > 0 e um n₀ tais que f(N) ≤ c·g(N) para todo o N ≥ n₀.

Como ler o que vê

As cinco linhas correspondem a um tamanho de entrada avaliado em cinco classes de crescimento, com todas as constantes definidas como 1 — portanto, são contagens de operações e não tempos de execução. No valor predefinido N = 100, leem-se 1, 7, 100, 664 e 10,000. O logaritmo é de base 2: log₂ 100 ≈ 6.64, motivo pelo qual O(log N) mostra 7 e O(N log N) mostra 664 em vez de 700.

Pressupõe: Que uma operação custa o mesmo que qualquer outra e que a contagem é exata e não medida. É isso que torna a comparação clara e, na mesma medida, abstrata — padrões de acesso à memória, comportamento da cache e disco ficam todos fora deste modelo, e em hardware real decidem habitualmente qual de dois algoritmos vence.
Falha quando: O limite não promete nada abaixo de n₀, e pode observar isso diretamente: defina N = 2 e as cinco classes leem 1, 1, 2, 2 e 4 — praticamente indistinguíveis. A ordenação garantida pela notação só surge quando N é grande, sendo assim que um método O(N²) com uma constante pequena pode superar um O(N log N) em todas as entradas que alguma vez venha a ter na prática.

Quando o crescimento supera qualquer otimização 🖖

O Big-O descreve como o trabalho cresce à medida que o tamanho da entrada aumenta. Um único laço cresce aproximadamente com N, laços aninhados costumam crescer com N², e a recursão ramificada pode crescer exponencialmente. A lição importante é a escala: com N pequeno, muitas abordagens parecem semelhantes, mas com N maior, a classe de crescimento domina o tempo de execução.

O teste de dobrar a entrada 🖖

A forma mais clara de sentir uma classe de crescimento é dobrar a entrada e observar o que acontece com o trabalho. Em O(log N) ele mal se mexe — a busca binária encontra um elemento entre um milhão em cerca de 20 comparações. Em O(N) o trabalho dobra, e em O(N²) quadruplica. Arraste o N nesta ferramenta e veja as diferenças passarem de invisíveis a esmagadoras.

Quando a classe mais rápida perde 🖖

Uma classe de crescimento menor não garante um programa mais rápido. Os cientistas da computação chamam as exceções de algoritmos galácticos: métodos com melhor notação Big-O cujo fator constante oculto é tão enorme que só superam os métodos simples em entradas maiores do que qualquer coisa no universo físico. Vários algoritmos recordistas de multiplicação de matrizes nunca são usados na prática exatamente por isso — o Big-O descarta silenciosamente as constantes que decidem a velocidade real.

Problema resolvido na íntegra

Onde se abre o fosso entre N log N e N ² 5 passos
Para N = 100, o painel apresenta 664 para N log N e 10 000 para N². Trata-se de um fator de apenas quinze — longe do abismo que as classes de complexidade deveriam representar. Descubra onde é que o abismo realmente se abre.
1. Comece pelos dois números. log₂ 100 é 6,6439, pelo que N log₂ N é 664 e N² é 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. A razão entre eles não é uma constante, e esse é todo o propósito das classes de complexidade. Ao dividir, o N simplifica-se uma vez, restando N/log N — uma quantidade que cresce sem limite, apenas devagar.
3. Para N = 100, é 15,1. Trata-se de um valor real mas pouco impressionante: uma aceleração de quinze vezes é o tipo de coisa que um melhor fator constante poderia proporcionar, o que é precisamente a razão pela qual os testes de desempenho em entradas pequenas induzem em erro.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Introduza agora um milhão. O logaritmo mal se moveu — de 6,6 para 19,9, um fator de três — enquanto N cresceu dez mil vezes. A razão é agora de 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. E nunca se inverte. A derivada de N/log N é positiva para todo o N superior a e, pelo que não existe qualquer tamanho de entrada a partir do qual o algoritmo quadrático o alcance.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Resposta

A ferramenta apresenta 664 contra 10 000 para N = 100. O número que vale a pena reter é o outro: num milhão, as mesmas duas curvas estão separadas por 50 172. As classes de complexidade não são afirmações sobre uma centena de elementos, e compará-las nesse ponto é a forma habitual de se convencer a escolher o algoritmo errado — um desfasamento de quinze vezes parece algo que uma linguagem mais rápida poderia fechar. Desloque o cursor para cima e observe a razão a acompanhar o movimento. É também por isso que o logaritmo é tão frequentemente ignorado na prática: cresceu por um fator de três enquanto a entrada cresceu dez mil vezes.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Percurso de aprendizagem

Contar trabalho, não segundos

Conduz a sorting-race

Referências (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

Pela equipa 42Math · Atualizado 2026-06-10

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

N pequeno = 20 - Todas as curvas em N=20
N=1000 - N=1000: as curvas polinomiais divergem
Escala log - A escala logarítmica revela as diferenças de crescimento
Constantes ocultas - Com c=50, 50N log N e N² cruzam-se perto de N=439