Introdução

Até então discutimos vários algoritmo de ordenação como alternativas para solucionar o mesmo problema. Dada uma sequência numérica $x_1,\dots,x_n$, reordenar a sequência de modo a produzir uma nova que respeite uma relação de ordem:

$x_i \leq x_{i+1}, \qquad i=1,\dots,n-1$

A comparação de eficiência entre os algoritmos discutidos tem sido feita considerando principalmente o pior caso de cada um, ou seja, sequências de entrada que levam esses algoritmos a terem seu pior desempenho, seja em tempo de execução ou número de comparações. Tal comparação teórica também pode ser feita em ao menos dois casos adicionais:

melhor caso, e
caso médio.

De forma genérica, o melhor caso de qualquer algoritmo representa tipos de entradas para as quais ele tem o seu melhor desempenho (menor número de comparações). Nos algoritmos de ordenação, isso geralmente ocorre quando a sequência já está ordenada da forma correta (ver tabela: buble sort e insertion sort).

O caso médio, por outro lado, representa o comportamento médio do algoritmo em todas as entradas possíveis. O desempenho médio desses algoritmos pode ser avaliado de forma aproximada por meio de experimentos. A tabela abaixo nos indica a complexidade de cada um dos algoritmos vistos até então nesses três casos.

Algoritmo	Melhor caso	Caso médio	Pior caso
Bubble sort	$O(n)$	$O(n^2)$	$O(n^2)$
Selection sort	$O(n^2)$	$O(n^2)$	$O(n^2)$
Insertion sort	$O(n)$	$O(n^2)$	$O(n^2)$
Quicksort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$
Mergesort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
Heapsort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$

Tais resultados teóricos nos dão um bom indicativo da eficiência relativa de cada um desses algoritmos. No entanto, caso dois algoritmos tenham a mesma complexidade teórica (ex.: quicksort, mergesort e heapsort) eles não são suficientes para dizermos qual algoritmo será mais “rápido” do ponto de vista prático. Isso ocorre pois na prática existem outras características que influenciarão o desempenho do algoritmo, como exemplo, podemos citar: forma de acesso à memória, menor número de trocas, qualidade da implementação, etc.

Algoritmos como o quicksort são muito úteis na prática. Porém, como eficiência nunca é demais, podemos nos perguntar: – “Não existiria algoritmo mais rápido?” –. O objetivo desta seção é oferecer uma resposta a essa pergunta.

Ordenação por comparações

Árvore de decisão

Ao examinarmos a implementação dos algoritmos acima podemos notar algo em comum. Todos eles utilizam comparações entre pares de elementos $x_i, x_j$ para determinar a ordem relativa entre esses elementos. Obviamente, cada uma dessas comparações pode oferecer como resposta, apenas uma dentre duas possibilidades que existem como resposta:

$x_i \leq x_j$, ou
$x_j \leq x_i$.

A ordem que os elementos serão comparados, ou a quantidade de vezes que um mesmo par de elementos será comparado depende de um algoritmo específico e portanto deve ser ignorado nessa análise.

O ponto mais importante seria notar que a cada comparação $x_i \leq x_j$, um determinado algoritmo ganha informação sobre a ordem relativa desses dois elementos. Se representarmos todas as possíveis sequências de comparações, temos uma estrutura chamada árvore binária de decisão.

decision-tree

Esse tipo de árvore representa as decisões tomadas por um algoritmo qualquer, em que cada nó inicia com a informação adicional obtida da comparação feita acima dele. Por exemplo, o nó 2:3 (o qual representa a comparação entre $x_2$ e $x_3$) já assume que $x_1\leq x_2$.

Altura da árvore de decisão

Os nós folhas da árvore indicam qual permutação da sequência original tornaria essa sequência ordenada de forma não decrescente. Por exemplo, <3,1,2>, no diz que a sequência ordenada é $x_3,x_1,x_2$.

É de se esperar que um algoritmo correto permita uma resposta correta para toda possível entrada. Se os nós folhas da árvore nos dão a permutação da entrada que produz a resposta correta, então devem existir ao menos $n!$ permutações como nós folhas, uma para cada possível entrada. Sabendo disso,

Qual seria o limitante inferior para a complexidade de qualquer algoritmo de ordenação por comparação?

A ordenação de uma sequência é o procedimento descrito como um caminho que inicia na raíz da árvore de decisão e chega até uma de suas folhas, portanto o número total de comparações é equivalente a altura da árvore.

Limitante Inferior

Um limitante inferior (lower-bound), como o próprio nome diz, limita por baixo a complexidade de algo. No nosso caso, esse algo é o problema de ordenação de uma sequência. Como temos discutido complexidade da ordenação em termos do número de comparações, esse limitante inferior nos dará uma estimativa do menor número comparações possível, que um algoritmo teria que fazer para conseguir ordenar uma sequência qualquer. Este limitante inferior é equivalente a altura da árvore de decisão.

Uma árvore binária qualquer tem, em seu $\ell$-ésimo nível, $2^\ell$ nós. Sabemos que o último nível dessa árvore deve ter no mínimo $n!$ nós, portanto, no último nível

$n! \leq 2^\ell$

Aplicando o logaritmo em ambos os lados

$\log(n!) \leq \ell$

Não nos preocuparemos com os detalhes da demonstração, mas a partir dessa desigualdade é possível chegar ao resultado.

$\ell \geq n \log n$

O qual significa que qualquer algoritmo de ordenação baseado em comparações terá que fazer no mínimo $n \log n$ comparações.

Qual seria o limitante inferior para a busca binária?

Siga a mesma ideia descrita acima para obter um limitante inferior para busca binária.

Referências

CORMEN, Thomas H. Desmistificando algoritmos. 1. ed. Rio de Janeiro, RJ: Elsevier, c2014. xii, 188 p. ISBN 9788535271775.(pdf:Algorithms Unlocked).
CORMEN, Thomas H. et al. Algoritmos: teoria e prática. Rio de Janeiro, RJ: Campus, 2002. xvii, 916 p. ISBN 8535209263. (pdf: Algoritmos)
MIT - https://www.youtube.com/watch?v=Nz1KZXbghj8