Preciso decorar a matemática do O(n log n)?

Não. Basta a intuição: n ao quadrado cresce rápido demais em listas grandes, e n log n cresce quase reto. O log n vem de cortar a lista pela metade várias vezes, como na busca binária. Guardar essa imagem já basta para escolher bem entre um método simples e um eficiente.

A bolha e a inserção são inúteis, então?

De jeito nenhum. São simples de entender e de escrever, e para listas pequenas ou quase ordenadas funcionam muito bem. A inserção, em particular, é ótima quando a lista já está quase ordenada. O ponto é que elas não escalam: em listas grandes, o custo n ao quadrado as derruba.

O que significa dizer que um algoritmo é O(alguma coisa)?

É uma forma de descrever como o custo cresce conforme a entrada aumenta, ignorando detalhes de máquina e constantes. O(n) cresce em linha reta, O(n ao quadrado) cresce como parábola, O(n log n) fica no meio, quase reto. Serve para comparar algoritmos sem depender do computador específico.

Existe ordenação mais rápida que O(n log n)?

Para ordenação por comparação, não: O(n log n) é o limite matemático. Existem métodos especiais que não comparam elementos, como a ordenação por contagem, que podem ser mais rápidos em casos específicos, por exemplo notas inteiras de 0 a 100. Mas eles exigem condições que nem sempre valem.

Por que dobrar a lista quadruplica o trabalho no método simples?

Porque o custo é proporcional a n ao quadrado. Se n vira 2n, então o custo vira 2n ao quadrado, que é 4 vezes n ao quadrado. Esse crescimento por quadrado é o que torna os métodos simples inviáveis assim que a lista passa de alguns milhares de itens.

Onde essa diferença aparece no dia a dia?

Em qualquer lugar que ordene muitos dados: uma loja online classificando produtos por preço, um aplicativo mostrando mensagens por data, um sistema organizando milhões de registros. Nesses casos, um algoritmo O(n log n) responde em frações de segundo onde um O(n ao quadrado) levaria minutos.

Módulo 9 - Ordenação eficiente: merge sort e quick sort

Por que O(n log n) ganha de O(n ao quadrado)

8 min de leitura · por Cesar Gargiulo, revisado pela equipe ValorFinal e GuardiaSec · Atualizado em 12/07/2026

Velocidade

O que você vai aprender

Relembrar por que os métodos simples de ordenação são O(n ao quadrado).
Entender o significado de O(n log n) de forma intuitiva.
Comparar as duas curvas de custo em listas grandes.
Reconhecer quando a eficiência da ordenação passa a importar de verdade.

O limite dos métodos simples

No curso intermediário você ordenou listas de três jeitos: comparando vizinhos e trocando (bolha), procurando o menor e colocando na frente (seleção) e encaixando cada item no lugar certo entre os já ordenados (inserção). Todos resolvem o problema, e para listas curtas nem dá para perceber diferença. O que eles têm em comum é o preço: cada elemento acaba comparado com muitos outros. Numa lista de n itens, isso dá algo próximo de n vezes n comparações, ou seja, n ao quadrado. Esse quadrado é o teto que segura os métodos simples. Ele não aparece em listas pequenas, mas cobra caro quando a lista cresce.

Pense em números concretos. Uma lista de 10 itens faz por volta de 100 comparações no pior caso, coisa instantânea. Uma lista de 1.000 itens já pula para cerca de 1 milhão de comparações. Uma de 1 milhão de itens chega perto de 1 trilhão de comparações, o que pode significar minutos ou horas de espera. O padrão é cruel: sempre que a lista dobra, o trabalho quadruplica, porque dois ao quadrado é quatro. Foi para escapar desse crescimento que se inventaram os métodos eficientes, e a chave deles é a técnica que abriu o módulo anterior, dividir para conquistar.

Gráfico com duas curvas partindo da origem. A curva de baixo, quase reta e crescendo devagar, está rotulada O(n log n) e representa merge sort e quick sort. A curva de cima, disparando para o alto num formato de parábola, está rotulada O(n ao quadrado) e representa bolha, seleção e inserção. Setas marcam o ponto em que a lista tem um milhão de itens, mostrando o abismo entre as duas curvas nesse tamanho. — As duas curvas quase se encostam em listas pequenas e se separam de forma dramática à medida que a lista cresce.

De onde vem o log n

O termo log n assusta pela notação, mas a ideia por trás é simples e você já viu na busca binária. Toda vez que um algoritmo corta o problema pela metade a cada passo, o número de passos até sobrar um item é o log na base dois do tamanho. Uma lista de 8 vira 4, vira 2, vira 1: três cortes, e log de 8 na base dois é 3. Uma lista de 1 milhão precisa de só cerca de 20 cortes pela metade. Esse número minúsculo, 20, é o log n. Ele cresce tão devagar que dobrar a lista soma apenas uma unidade a ele. É isso que torna O(n log n) quase tão bom quanto percorrer a lista uma vez.

🎮 Jogo da aula

Verdade ou mito sobre custo

Decida se cada afirmação sobre eficiência de ordenação é verdadeira ou falsa.

Quando a eficiência importa mesmo

Nem sempre vale trocar um algoritmo simples por um eficiente. Se você ordena uma lista de 20 nomes uma vez por dia, a bolha resolve e ninguém percebe. A eficiência começa a pesar em três situações: listas grandes, ordenações repetidas muitas vezes por segundo e sistemas com prazo apertado de resposta. Um site que ordena milhares de produtos a cada busca, um banco que classifica milhões de transações, um jogo que reorganiza objetos a cada quadro na tela, todos sentem a diferença entre as duas curvas. Escolher o algoritmo certo não é firula: é a diferença entre um programa que responde na hora e um que trava.

Teste rápido

Por que O(n log n) supera O(n ao quadrado) justamente em listas grandes?

Perguntas frequentes

Preciso decorar a matemática do O(n log n)?: Não. Basta a intuição: n ao quadrado cresce rápido demais em listas grandes, e n log n cresce quase reto. O log n vem de cortar a lista pela metade várias vezes, como na busca binária. Guardar essa imagem já basta para escolher bem entre um método simples e um eficiente.
A bolha e a inserção são inúteis, então?: De jeito nenhum. São simples de entender e de escrever, e para listas pequenas ou quase ordenadas funcionam muito bem. A inserção, em particular, é ótima quando a lista já está quase ordenada. O ponto é que elas não escalam: em listas grandes, o custo n ao quadrado as derruba.
O que significa dizer que um algoritmo é O(alguma coisa)?: É uma forma de descrever como o custo cresce conforme a entrada aumenta, ignorando detalhes de máquina e constantes. O(n) cresce em linha reta, O(n ao quadrado) cresce como parábola, O(n log n) fica no meio, quase reto. Serve para comparar algoritmos sem depender do computador específico.
Existe ordenação mais rápida que O(n log n)?: Para ordenação por comparação, não: O(n log n) é o limite matemático. Existem métodos especiais que não comparam elementos, como a ordenação por contagem, que podem ser mais rápidos em casos específicos, por exemplo notas inteiras de 0 a 100. Mas eles exigem condições que nem sempre valem.
Por que dobrar a lista quadruplica o trabalho no método simples?: Porque o custo é proporcional a n ao quadrado. Se n vira 2n, então o custo vira 2n ao quadrado, que é 4 vezes n ao quadrado. Esse crescimento por quadrado é o que torna os métodos simples inviáveis assim que a lista passa de alguns milhares de itens.
Onde essa diferença aparece no dia a dia?: Em qualquer lugar que ordene muitos dados: uma loja online classificando produtos por preço, um aplicativo mostrando mensagens por data, um sistema organizando milhões de registros. Nesses casos, um algoritmo O(n log n) responde em frações de segundo onde um O(n ao quadrado) levaria minutos.

Fontes

Seu progresso fica salvo neste aparelho. Assinantes sincronizam entre os aparelhos.

← Recursão ou iteração: qual escolher Concluir e avançar →