Mostre que a ordem de torneio exige \Theta(n \log n) comparações para ordenar uma lista de n elementos. [Dica: Pela inserção de um número adequado de elementos fictícios definido
como menor do que todos os inteiros, tal como -\infty, suponha que n=2^{\mathrm{k}} para algum inteiro positivo k.]

Passo 1

O enunciado pede para mostrar que o método de ordenação por torneio (selection tree) usa \Theta(n\log n) comparações em uma lista de n elementos. A ideia é preencher até o próximo valor de potência de 2, usando elementos fictícios com valor -\infty, para ter uma árvore completa de altura k com n=2^k. Vamos então contabilizar as comparações necessárias na construção da árvore e em cada extração do mínimo.

Passo 2

Construção inicial da árvore de torneio:
— Colocamos os n elementos em folhas de uma árvore completa de tamanho 2^k.
— Em cada nó interno, comparamos os valores de seus dois filhos e guardamos o vencedor (o menor).
Como há exatamente 2^k-1=n-1 nós internos, a construção faz n-1
comparações.

Passo 3

Extração de um elemento (o mínimo):
— O mínimo está na raiz. Para “remover” esse valor e continuar a ordenação, substituímos a folha correspondente por -\infty.
— Subimos pela árvore recomparando em cada nível: em cada nó interno acima da folha substituída, comparamos os dois filhos para decidir o novo vencedor.
Como a altura da árvore é k=\log_2 n, cada extração gasta
\log_2 n
comparações.

Passo 4

Complexidade total:
— Construção inicial: n-1 comparações.
— Extração de todos os n elementos: n\cdot \log_2 n comparações.
Somando, o custo total é
(n-1) + n\log_2 n = \Theta(n\log n).

Resposta

\Theta(n\log n)

Exercícios de Livros Relacionados