Encontrar los 2 números más altos: informática

Question

Estoy tratando de encontrar un algoritmo para encontrar los 2 números más altos en una lista de números.

El número más alto se puede encontrar en n-1 etapas, tal vez haciendo el primer paso de una burbuja de ordenación o algo por el estilo. Para mí, parece que encontrar el siguiente número más alto también podría encontrarse en un total de 1.5n comparaciones en promedio.

Mi profesor nos preparó la tarea para escribir un alogrithm que encuentre los 2 números más altos en n + log (n) comparaciones. ¿Esto es posible? Alguna idea, sugerencia?

Editar: Cuando digo n + log (n) No me refiero a O (n + n log), sino más bien exactamente n + log n

Answer 1

Sí, es posible hacerlo en no más de (n + log n). Realmente no puedo decirte cómo sin dar la respuesta, pero déjame intentarlo. :-)

Tome los n números, compárelos en pares a la vez. Tome el ceil (n/2) "ganadores", y repita, "como un árbol binario". Preguntas: ¿Cuántas comparaciones se necesitan para encontrar la más grande? ¿A cuántas personas gana esta victoria "ganadora"? ¿A quién podría haber perdido el segundo más grande? Entonces, ¿cuántas comparaciones toma ahora para encontrar el segundo número más grande?

La respuesta resulta ser un total de n-1 + techo (log n) - 1 comparaciones, donde el registro está en la base 2. También puede demostrar usando un argumento contradictorio que no es posible hazlo mejor que esto en el peor de los casos.

Answer 2

¿Qué tal esto:

for each listOfNumbers as number 
    if number > secondHighest 
     if number > highest 
      secondHighest = highest 
      highest = number 
     else 
      secondHighest = number 

Answer 3

Editar: Oops, se perdió una cosa simple debido a la estupidez. Esta solución no es correcta, aunque la mantengo aquí ya que todavía es prom (n + log (n)). Gracias a ShreevatsaR por señalar mi estupidez. Sí consideré la búsqueda en árbol, pero olvidé por completo la idea de retroceder para encontrar el segundo número más alto en log (n).

De todos modos, aquí sigue mi prueba de por qué el algoritmo inferior no es más que avg (n + log (n)). En la vida real todavía debería funcionar bastante bien al menos.

• Primera comparación contra el segundo número más alto registrado.
• Solo si esa comparación tiene éxito, compárela con el número más alto registrado.

Para demostrar que es en promedio n + log n, simplemente tenemos que demostrar que la primera comparación solo tiene éxito en log (n) veces en promedio. Y eso es bastante simple de ver o demostrar.

1. Supongamos P como el de la posición real de la corriente segundo número más grande en una versión ordenada de la lista, y ejecutar el algoritmo
2. Si P> 2 a continuación, cuando se encuentra un número mayor, la nueva p en promedio no será más que P/2.
3. Si P = 2, entonces la primera comparación no puede tener éxito, ya que no hay un número que sea mayor que el segundo número más grande actual.
4. P a lo sumo igual N
5. De 2, 3 y 4 debe ser trivial ver que la primera comparación no puede tener más éxito que el log (N) veces en promedio.

Answer 4

La respuesta publicada por ShreevatsaR parece ser O (n log n).

La primera pasada (n operaciones) produce n/2 respuestas. Al repetir, supongo que te refieres a que harás n/2 operaciones para producir n/4 respuestas. Pasará por el registro de bucles n veces. Esto es muy parecido a un tipo de combinación, excepto que la clase de fusión siempre procesa n nodos cada vez que pasa. También ejecuta el registro de bucle n veces. Y no veo cómo este algoritmo hará un seguimiento del segundo número más alto.

nickf tiene la respuesta correcta. El peor caso es cuando la lista está ordenada, hará 2n comparaciones, eso es O (n).

por cierto, O (n + log n) es O (n) la notación de orden se refiere al crecimiento asintótico en el peor de los casos.

Answer 5

Puede usar clasificación de conteo, clasificación de radix, ordenación de cuchara u otro algoritmo de tiempo lineal para primero ordenar la lista en orden descendente. Luego solo obtenga los primeros 2 elementos de la lista ordenada. Esto tomará (n) + 2 = (n)

Tenga en cuenta que estos algoritmos pueden ordenar en tiempo lineal porque cada uno tiene sus propias suposiciones.

Answer 6

Pseudocódigo (no es esta esencia n?)

int highestNum = 0 
int secondHighest = highestNum 

for(i = 0; i < list.length; i++) 
{ 
if(list[i] >= highestNum) 
{ 
secondHighest = highestNum 
highestNum = list[i] 
} 
}