Este es un rompecabezas muy conocido para encontrar el segundo elemento máximo de elementos distintos. La respuesta en general sería (n + log2 (n) -2). Entonces la respuesta para n = 32 sería 35.
Veamos cómo lo harías para n = 8 prácticamente.
Piense de esta manera que las bolas están dispuestas en el suelo.
Ahora, en cada etapa, comience a comparar los pares consecutivos de bolas, actualice a los ganadores al siguiente nivel y colóquelos entre los dos puntos anteriores de las bolas que comparó, mientras obtiene un ganador final que es la bola más pesada.
- Si usted fuera un observador experto, ¿cuál sería su opinión sobre las ubicaciones geográficas de este entorno?
- ¿Por qué los escritores de crucigramas están obsesionados con las espada?
- A puede completar un trabajo en 16 días y B en 12 días. Comenzando con A, trabajan en días alternos. ¿El trabajo total se completará en cuántos días?
- Si la gravedad es una fuerza tan débil, ¿por qué es tan dominante?
- ¿Cuáles son algunos trucos lowbrow?
Entonces, después del primer paso, digamos que tienes (* representa una bola y B representa un espacio en blanco):
* * * *
* BB * * B * B
Y luego, después de obtener el ganador, supongamos una situación como esta:
* *
* b
* B b *
* BB * * b * B
Aquí he representado el camino de los ganadores con ‘b’, también es un espacio en blanco, pero en algún momento fue adquirido por el ganador.
Ahora no tienes que encontrar el ganador, tienes que encontrar el segundo mejor: P.
Te das cuenta de que el segundo mejor podría haber perdido en algún momento por el ganador.
Si siguió los pasos anteriores, es más fácil encontrar a los perdedores que al ganador. El segundo más grande sería el máximo de todos los perdedores al ganador. Empiezas desde la posición del ganador desde la parte superior y compruebas a sus hijos, uno sería un perdedor y el otro sería un espacio en blanco. Compare al niño perdedor ya que podría ser el segundo más pesado y muévase al espacio en blanco. Repita hasta llegar al fondo.
Análisis de complejidad:
n-1 comparaciones para obtener el ganador. (en nuestro caso: n = [matemáticas] 2 ^ k [/ matemáticas], entonces [matemáticas] 2 ^ {k-1} + 2 ^ {k-2} +… = 2 ^ k – 1 = n-1 [/ matemáticas])
log2 (n) -1 comparaciones para obtener el máximo de perdedores para el ganador (puede ver que si ignoramos los espacios en blanco y los asumimos como elementos, en realidad es un árbol binario. Entonces, el número de perdedores para el ganador = altura del árbol binario).
Movimientos totales: n + log2 (n) -2.