next up previous
Next: About this document ...

MAC 5711 - An�lise de Algoritmos
Departamento de Ci�ncia da Computa��o
Primeiro semestre de 2004



Limite inferior para ordena��o



Vimos em aula v�rios algoritmos de ordena��o. Alguns tinham complexidade de pior caso $ \Theta(n^2)$, outros tinham complexidade de pior caso $ \Theta(n \log n)$. 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 $ n$, 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 $ a_1,\ldots,a_n$ os elementos de uma seq��ncia arbitr�ria de entrada de tamanho $ n$. 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_i \leq a_j$''.

A �rvore de decis�o de um tal algoritmo (definida para cada valor de $ n$) � uma �rvore bin�ria cujos v�rtices internos est�o rotulados por pares de elementos da seq��ncia de entrada, denotados por exemplo por $ a_i:a_j$. Cada v�rtice interno tem dois filhos. As arestas de um v�rtice interno para os seus filhos est�o rotuladas uma por $ \leq$ e a outra por $ >$. Para facilitar a exposi��o, digamos que o r�tulo $ \leq$ leva ao filho esquerdo e que o r�tulo $ >$ leva ao filho direito. Cada folha est� rotulada por uma permuta��o de $ 1\,.\,.\,n$. 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_1,\ldots,a_n$. A sub�rvore esquerda da raiz descreve as compara��es subseq�entes, caso o resultado desta primeira compara��o, digamos, $ a_i \leq a_j$, seja verdadeiro. J� a sub�rvore direita descreve as compara��es subseq�entes caso o resultado da compara��o $ a_i \leq a_j$ seja falso. Com isso, cada seq��ncia $ a_1,\ldots,a_n$ 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 $ a_1,\ldots,a_n$ ordenada.


Exemplo: A �rvore de decis�o do algoritmo inser��o para $ n=3$ �

Por exemplo, se $ a_1=10$, $ a_2=5$ e $ a_3=7$, o ``caminho'' do algoritmo na �rvore de decis�o acima � o caminho marcado em negrito.

Note que cada uma das $ 3!$ permuta��es aparece nas folhas. Isso � de se esperar mesmo para um $ n$ arbitr�rio. Ou seja, cada uma das $ n!$ 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 $ n!$ permuta��es de $ 1\,.\,.\,n$. Cada uma delas deve aparecer em alguma das folhas da �rvore de decis�o. Portanto, a �rvore de decis�o deve ter pelo menos $ n!$ folhas. Por outro lado, uma �rvore bin�ria de altura $ h$ tem no m�ximo $ 2^h$ folhas. Assim, se $ h$ � a altura da �rvore de decis�o de um algoritmo de ordena��o baseado em compara��es, ent�o $ 2^h \geq n!$. Sabemos, pela f�rmula de Stirling, que

$\displaystyle n! \ \geq \big(\frac{n}{e}\big)^n.$

Ent�o, podemos concluir que

$\displaystyle h \ \geq \ \log n! \ \geq \ \log \big(\frac{n}{e}\big)^n \ = \ n\,\log \frac{n}{e} \ = \ n (\log {n} - \log e) \ = \ \Omega(n \log n).$

Portanto, de fato, qualquer algoritmo de ordena��o baseado em compara��es tem complexidade de pior caso $ \Omega(n \log n)$.



Exerc�cios

  1. Construa a �rvore de decis�o para o algoritmo Mergesort para $ n=4$. Quais as permuta��es de pior caso?

  2. Construa a �rvore de decis�o do algoritmo Quicksort (vers�o n�o-probabil�stica) para $ n=3$. Quais as permuta��es de pior caso?

  3. Por que a hip�tese de que os elementos s�o todos distintos na an�lise acima n�o � restritiva? (Ou seja, por que ela n�o impede que concluamos que o algoritmo, para inst�ncias arbitr�rias, consome tempo de pior caso $ \Omega(n \log n)$?)

  4. Mostre que qualquer algoritmo de busca baseado em compara��es faz no pior caso pelo menos $ \lceil{\log n}\rceil $ compara��es. Um algoritmo de busca � um algoritmo que determina uma posi��o em que um elemento $ x$ aparece em um dado vetor $ v[0..n-1]$. Um algoritmo de busca baseia-se em compara��es se o seu fluxo de controle depende apenas de compara��es envolvendo elementos do vetor e $ x$.


next up previous
Next: About this document ...
Cristina Gomes Fernandes
2004-04-01