Supondo que
, o número de elementos a serem ordenados, seja igual a
para algum inteiro positivo
, 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
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
elementos são agrupados em
pares, e em cada par fazemos uma comparação para eleger o “vencedor” que passa para a próxima fase. Logo, nesta rodada temos
comparações.
Passo 3
Na segunda rodada sobram
vencedores, que formam
pares. Assim fazemos
comparações. De modo geral, na rodada
(contando
para a primeira rodada) sobrará
elementos formando
pares, e portanto fazemos
comparações.
Passo 4
Ao todo há
rodadas (porque
e a cada rodada o número de elementos é dividido por 2 até chegar a 1). Então o total de comparações é
pois
.
Resposta
O número de comparações é
, isto é,
.