João diz ter desenvolvido um algoritmo que é capaz de ordenar qualquer conjunto de
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
comparações para ordenar qualquer sequência de
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
folhas (uma para cada permutação de
elementos).
Passo 3
Seja
a altura da árvore (o número máximo de comparações no pior caso). Como é uma árvore binária, temos
pois com
níveis podemos distinguir no máximo
folhas.
Passo 4
Aplicando logaritmo na base 2 em ambos os lados da desigualdade, obtemos
E pelo uso da aproximação de Stirling, sabemos que
ou seja, qualquer algoritmo de ordenação por comparação precisa de pelo menos
comparações no pior caso.
Passo 5
Como
cresce mais lentamente do que
para grandes
, o algoritmo de João, que faria apenas
comparações, violaria esse limite inferior. Logo, é impossível ordenar qualquer conjunto de
reais apenas com
comparações.
Resposta
Não compraria, pois qualquer algoritmo de ordenação por comparações exige no mínimo
comparações, e
fica abaixo desse limite para grandes
.