Supondo que n, o número de elementos a serem ordenados, seja igual a 2^{k} para algum inteiro positivo k, determine o número de comparações usadas na ordem de torneio para encontrar o maior elemento da lista usando a ordem de torneio.

Passo 1

O enunciado diz que temos uma lista com n=2^{k} elementos e queremos encontrar o maior usando o método de “ordem de torneio”, isto é, comparando pares de elementos em rodadas eliminatórias até restar apenas o vencedor (o maior). O conteúdo aqui é simplesmente contar quantas comparações são feitas em cada rodada de um torneio completo em árvore binária.

Passo 2

Na primeira rodada todos os n elementos são agrupados em \tfrac{n}{2} pares, e em cada par fazemos uma comparação para eleger o “vencedor” que passa para a próxima fase. Logo, nesta rodada temos
\frac{n}{2}
comparações.

Passo 3

Na segunda rodada sobram \tfrac{n}{2} vencedores, que formam \tfrac{n}{4} pares. Assim fazemos
\frac{n}{4}
comparações. De modo geral, na rodada j (contando j=1 para a primeira rodada) sobrará \tfrac{n}{2^{j-1}} elementos formando \tfrac{n}{2^{j}} pares, e portanto fazemos
\frac{n}{2^{j}}
comparações.

Passo 4

Ao todo há k rodadas (porque n=2^{k} e a cada rodada o número de elementos é dividido por 2 até chegar a 1). Então o total de comparações é
\sum_{j=1}^{k}\frac{n}{2^{j}} =\;n\sum_{j=1}^{k}\frac{1}{2^{j}} =\;n\Bigl(1-\frac{1}{2^{k}}\Bigr) =\;n-1
pois \sum_{j=1}^{k}2^{-j}=1-2^{-k}.

Resposta

O número de comparações é n-1, isto é, 2^{k}-1.

Exercícios de Livros Relacionados