Order statistics

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as seguintes afirmações:

I - Para localizar o maior valor em uma lista desordenada são necessárias, no mínimo, n-1 comparações entre seus n elementos.
II - Para encontrar o segundo maior valor em uma lista com n elementos, são necessárias n + ⌈ lg n ⌉ - 1 comparações no pior caso.
III - Comparando-se aos pares, os n elementos de uma lista, até que sobre apenas o menor valor, gera um total mínimo de ⌊ n^{(1+1/lg n)}⁄ 2 ⌋ - 1 comparações.

Assinale a alternativa correta:

a. Apenas I está correta.
b. I e II estão corretas.
c. I e III estão corretas.
d. II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller