Vimos em aula vários algoritmos de ordenação. Alguns tinham
complexidade de pior caso
, outros tinham complexidade de
pior caso
. Será que existem algoritmos de ordenação
com complexidade de pior caso melhor que estes?
Vamos mostrar que a resposta a esta pergunta é ``não'', pelo menos para algoritmos como os que vimos até agora, baseados em comparações.
Dizemos que um algoritmo de ordenação baseia-se em comparações
se, para seqüências de entrada de tamanho , o fluxo do algoritmo
depende apenas do resultado de comparações entre elementos da
seqüência.
Considere um algoritmo de ordenação arbitrário que se baseie em
comparações e denote por
os elementos de uma
seqüência arbitrária de entrada de tamanho
. Suponha, sem perda de
generalidade, que os elementos da seqüência são todos distintos. Neste
caso, podemos supor, também sem perda de generalidade, que todas as
comparações feitas pelo algoritmo são do tipo ``
''.
A árvore de decisão de um tal algoritmo (definida para cada
valor de ) é uma árvore binária cujos vértices internos estão
rotulados por pares de elementos da seqüência de entrada, denotados
por exemplo por
. Cada vértice interno tem dois filhos. As
arestas de um vértice interno para os seus filhos estão rotuladas uma
por
e a outra por
. Para facilitar a exposição, digamos que
o rótulo
leva ao filho esquerdo e que o rótulo
leva ao
filho direito. Cada folha está rotulada por uma permutação de
.
A árvore de decisão está associada ao algoritmo da seguinte maneira. O
rótulo da raiz da árvore corresponde à primeira comparação efetuada
pelo algoritmo quando a entrada é uma seqüência
. A
subárvore esquerda da raiz descreve as comparações subseqüentes, caso
o resultado desta primeira comparação, digamos,
, seja
verdadeiro. Já a subárvore direita descreve as comparações
subseqüentes caso o resultado da comparação
seja falso.
Com isso, cada seqüência
corresponde a um caminho da
raiz até uma folha da árvore de decisão. A permutação que rotula essa
folha é exatamente a permutação que deixa
ordenada.
Exemplo: A árvore de decisão do algoritmo inserção para
é
Por exemplo, se ,
e
, o ``caminho'' do
algoritmo na árvore de decisão acima é o caminho marcado em negrito.
Note que cada uma das permutações aparece nas folhas. Isso é de
se esperar mesmo para um
arbitrário. Ou seja, cada uma das
permutações deve aparecer como rótulo de uma das folhas na árvore de
decisão. Afinal, para cada permutação específica, há pelo menos uma
seqüência de entrada que é ordenada apenas por aquela permutação.
Se uma permutação não aparecesse, então o algoritmo não ordenaria a
correspondente seqüência de entrada.
Observe também que o número de comparações que o algoritmo faz no pior caso é exatamente a altura da árvore de decisão. Portanto, se calcularmos uma delimitação inferior para a altura da árvore de decisão do algoritmo, temos uma delimitação inferior para a complexidade de pior caso do algoritmo. Isso é o que vamos fazer.
Existem permutações de
. Cada uma delas deve aparecer em
alguma das folhas da árvore de decisão. Portanto, a árvore de decisão
deve ter pelo menos
folhas. Por outro lado, uma árvore binária de
altura
tem no máximo
folhas. Assim, se
é a altura da
árvore de decisão de um algoritmo de ordenação baseado em comparações,
então
. Sabemos, pela fórmula de Stirling, que
Exercícios