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 las etapas n-1, quizás haciendo el primer paso de una burbuja 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 asignó la tarea para escribir un algoritmo que encuentre los 2 números más altos en n + log (n) comparaciones. ¿Es esto posible? ¿Alguna idea, sugerencia?

Editar: cuando digo n + log (n) no me estoy refiriendo a O (n + log n), 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 techo (n / 2) "ganadores" y repita "como un árbol binario". Preguntas: ¿cuántas comparaciones se necesitan para encontrar la más grande? ¿Cuántas personas hace este " ganador " ganar contra? ¿A quién podría haber perdido el segundo más grande? Entonces, ¿cuántas comparaciones se necesitan 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 es la base 2. También puede probar usando un argumento de confrontación que no es posible hacerlo mejor que esto en el peor de los casos.

Answer 2

Editar: Vaya, se perdió algo simple debido a la estupidez. Esta solución no es correcta, aunque la mantengo aquí, ya que todavía es avg (n + log (n)). Gracias a ShreevatsaR por señalar mi estupidez. Consideré la búsqueda de árbol, pero perdí 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, al menos debería funcionar bastante bien.

• Primero compare con el segundo número más alto registrado.
• Solo si esa comparación tiene éxito, compare 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 log (n) veces en promedio. Y eso es bastante simple de ver o demostrar.

1. Suponga que P es la posición real del segundo número más grande actual en una versión ordenada de la lista, y ejecute el algoritmo
2. Si P > 2, entonces, cuando se encuentre 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 puede como máximo N
5. A partir de 2, 3 y 4, debería ser trivial ver que la primera comparación no puede tener más éxito que log (N) veces en promedio.

Answer 3

¿Qué tal esto?

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

Answer 4

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

El primer pase (n operaciones) produce n / 2 respuestas. Al repetir, supongo que quieres decir que harás n / 2 operaciones para producir n / 4 respuestas. Recorrerás el registro de bucle n veces. Esto es muy parecido a una ordenación por fusión, excepto que la ordenación por fusión siempre procesa n nodos cada vez. 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 grande.

nickf tiene la respuesta correcta. el peor de los casos es cuando se ordena la lista, hará 2n comparaciones, es decir, O (n).

por cierto, O (n + log n) es O (n) la notación de Orden se refiere al peor crecimiento asintótico del caso.

Answer 5

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

Tenga en cuenta que estos algoritmos pueden clasificarse en tiempo lineal porque cada uno tiene sus propios supuestos.

Answer 6

Pseudocódigo (¿no es esto esencialmente n?)

int highestNum = 0
int secondHighest = highestNum

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