João diz ter desenvolvido um algoritmo que é capaz de ordenar qualquer conjunto de n números reais, fazendo apenas comparações. Você compraria este algoritmo? Justifique.

Passo 1

O enunciado diz que João afirma ter um algoritmo de ordenação por comparações que usa apenas O(n^3/2) comparações para ordenar qualquer sequência de n números reais. Estamos numa aula de complexidade de algoritmos e vamos usar o modelo de árvore de decisão para comparação para verificar se isso é plausível.

Passo 2

Em ordenação por comparações, cada execução do algoritmo corresponde a um caminho numa árvore binária de decisões, onde cada nó é uma comparação entre dois elementos. Cada folha da árvore representa uma permutação possível da entrada ordenada. Para que o algoritmo esteja correto para todas as entradas, a árvore deve ter pelo menos n! folhas (uma para cada permutação de n elementos).

Passo 3

Seja h a altura da árvore (o número máximo de comparações no pior caso). Como é uma árvore binária, temos
2^h >= n!
pois com h níveis podemos distinguir no máximo 2^h folhas.

Passo 4

Aplicando logaritmo na base 2 em ambos os lados da desigualdade, obtemos
h >= log2(n!)
E pelo uso da aproximação de Stirling, sabemos que
log2(n!) = Theta(nlog2 n)
ou seja, qualquer algoritmo de ordenação por comparação precisa de pelo menos Omega(nlog n) comparações no pior caso.

Passo 5

Como n^3/2 cresce mais lentamente do que nlog n para grandes n, o algoritmo de João, que faria apenas O(n^3/2) comparações, violaria esse limite inferior. Logo, é impossível ordenar qualquer conjunto de n reais apenas com O(n^3/2) comparações.

Resposta

Não compraria, pois qualquer algoritmo de ordenação por comparações exige no mínimo Omega(nlog n) comparações, e O(n^3/2) fica abaixo desse limite para grandes n.

Exercícios relacionados