Quantas comparações a ordem de torneio usa para encontrar o segundo maior elemento, o terceiro maior elemento e assim por diante, até o ( n-1 )-ésimo maior (ou o segundo menor) elemento?

Passo 1

O método “ordem de torneio” organiza os n elementos numa árvore de competições: cada partida compara dois elementos e o vencedor sobe ao nível seguinte. Após n-1 comparações obtemos o maior elemento. Guardamos, para cada vencedor, a lista dos elementos que ele derrotou ao longo do torneio. Se n for potência de 2, a altura da árvore é
m = \log_{2}n.
Para generalizar a caso arbitrário de n, trocaremos depois m por \lceil\log_{2}n\rceil.

Passo 2

Após o torneio inicial (que custou n-1 comparações), o máximo geral x_{(1)} derrotou exatamente m oponentes. Para encontrar o segundo maior x_{(2)} basta achar o máximo entre esses m elementos – isto são mais m-1 comparações. Logo, o total de comparações para obter o segundo maior é
C(2) \;=\; (n-1) \;+\; (m-1).

Passo 3

O vencedor dessa mini-disputa pelos perdedores de x_{(1)} é x_{(2)}. Ele próprio derrotou nos m níveis originais exatamente (m-1) oponentes (todos, exceto aquele que o venceu). Para achar o terceiro maior x_{(3)} comparamos agora esses (m-1) elementos em (m-2) novos confrontos. O total até aqui é
C(3) \;=\; (n-1) \;+\; (m-1) \;+\; (m-2).

Passo 4

Prosseguindo, para cada k=2,3,\dots,n-1, o k-ésimo maior x_{(k)} surge como o campeão dos perdedores de x_{(k-1)}, que foram (m-(k-2)) elementos e exigem (m-(k-2)-1)=m-k+1 comparações.

Passo 5

Somando tudo, o número de comparações para encontrar o k-ésimo maior é
C(k) =\;(n-1) \;+\;\sum_{i=1}^{k-1}\bigl(m - i\bigr) =\;(n-1)\;+\;(k-1)\,m \;-\;\frac{(k-1)\,k}{2}.

Passo 6

Se n não é potência de 2, basta tomar
m = \lceil\log_{2}n\rceil
e a fórmula continua valendo em termos de limite superior de comparações. Em particular, para k=n-1 (ou seja, até o segundo menor) temos
C(n-1) =(n-1)+ (n-2)\,\lceil\log_{2}n\rceil \;-\;\frac{(n-2)(n-1)}{2}.

Resposta

Para n=2^{m}:
\boxed{C(k)=(n-1)+(k-1)\,m-\frac{(k-1)\,k}{2},\quad k=2,\dots,n-1.}
Em geral basta substituir m=\lceil\log_{2}n\rceil.

Exercícios de Livros Relacionados