Trouver les 2 meilleurs chiffres - informatique

Question

J'essaie de trouver un algorithme pour trouver les 2 nombres les plus élevés dans une liste de nombres.

Le nombre le plus élevé peut être trouvé dans les n-1 étapes, peut-être en effectuant la première étape d'une sorte de bulle ou quelque chose du genre. Il me semble que trouver le nombre immédiatement supérieur le plus élevé pourrait être trouvé dans un total de 1,5n comparaisons en moyenne.

Mon professeur nous a demandé d’écrire un algorithme qui trouve les 2 nombres les plus élevés dans les comparaisons n + log (n). Est-ce seulement possible? Des idées, des suggestions?

Éditer: quand je dis n + log (n), je ne fais pas référence à O (n + log n), mais plutôt exactement n + log n

Answer 1

Oui, il est possible de le faire en pas plus de (n + log n). Je ne peux vraiment pas vous dire comment sans donner la réponse, mais laissez-moi essayer. :-)

Prenez les n nombres, comparez-les par paires à la fois. Prenez le ceil (n / 2) "gagnants" et répétez-le, "comme un arbre binaire". Questions: combien de comparaisons faut-il pour trouver le plus grand? Combien de personnes font ce "gagnant"? gagner contre? À qui le deuxième aurait-il pu perdre? Alors, combien de comparaisons faut-il maintenant pour trouver le deuxième plus grand nombre?

La réponse s'avère être un total de n-1 + plafonds (log n) - 1 , le journal étant basé sur la base 2. Vous pouvez également prouver à l'aide d'un argument contradictoire qu'il n'est pas possible de faire mieux que cela dans le pire des cas.

Answer 2

Edit: Oups, vous avez manqué une chose simple à cause de la stupidité. Cette solution n'est pas correcte, même si je la conserve ici car elle est toujours moyenne (n + log (n)). Merci à ShreevatsaR d’avoir signalé ma stupidité. J'ai bien envisagé la recherche dans les arbres, mais j'ai complètement manqué l’idée de revenir en arrière pour trouver le deuxième nombre le plus élevé dans log (n).

Quoi qu'il en soit, voici ma preuve pour expliquer pourquoi l’algorithme inférieur n’est autre que avg (n + log (n)). Dans la vraie vie, il devrait quand même bien fonctionner, du moins.

• Première comparaison avec le deuxième plus grand nombre enregistré.
• Seulement si cette comparaison réussit, comparez avec le plus grand nombre enregistré.

Pour prouver que n + log n est en moyenne, il suffit de prouver que la première comparaison réussit seulement log (n) fois en moyenne. Et c'est assez simple à voir ou à démontrer.

1. Supposons que P est la position réelle du deuxième plus grand nombre actuel dans une version triée de la liste, puis exécutez l'algorithme
2. Si P> 2, lorsqu'un nombre plus important est trouvé, le nouveau P ne sera en moyenne pas supérieur à P / 2.
3. Si P = 2, la première comparaison ne peut aboutir car aucun nombre n'est supérieur au deuxième plus grand nombre en cours.
4. P peut au plus être égal à N
5. À partir de 2, 3 et 4, il devrait être facile de voir que la première comparaison ne peut pas réussir plus de log (N) fois en moyenne.

Answer 3

Que diriez-vous de cela:

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

Answer 4

La réponse publiée par ShreevatsaR semble être O (n log n).

La première passe (n opérations) produit n / 2 réponses. En répétant, vous voulez dire que vous ferez n / 2 opérations pour produire n / 4 réponses. Vous parcourez le journal de boucle n fois. Cela ressemble beaucoup à un type de fusion sauf que ce type de fusion traite toujours n nœuds à chaque fois. Il exécute également le journal de boucle n fois. Et je ne vois pas comment cet algorithme gardera trace du deuxième plus grand nombre.

nickf a la bonne réponse. Dans le pire des cas, lorsque la liste est triée, il effectue 2n comparaisons - c’est-à-dire O (n).

btw, O (n + log n) est O (n) la notation de commande fait référence à la croissance asymptotique dans le pire des cas.

Answer 5

Vous pouvez utiliser le tri par comptage, le tri par base, le tri par seau ou un autre algorithme temporel linéaire pour trier d'abord la liste dans l'ordre décroissant. Ensuite, récupérez les 2 premiers éléments de la liste triée. Donc, cela prendra (n) + 2 = (n)

Notez que ces algorithmes peuvent trier en temps linéaire car chacun a ses propres hypothèses.

Answer 6

Pseudocode (n'est-ce pas essentiellement n?)

int highestNum = 0
int secondHighest = highestNum

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