Recherche du plus grand et du deuxième plus grand nombre de N

Question

Étant donné n nombres, comment puis-je trouver le plus grand et le deuxième plus grand nombre en utilisant au plus n + log (n) des comparaisons? Notez que ce ne sont pas les comparaisons O (n + log (n)), mais vraiment n + log (n).

Answer 1

pajton a fait un commentaire.

Laissez-moi élaborer.

Comme l'a dit pajton, cela peut être fait par la sélection du tournoi. Pensez à cela comme un tournoi de tennis en simple à élimination directe, où les capacités des joueurs ont un ordre strict et le résultat d'un match est décidé uniquement par cet ordre.

Au premier tour, la moitié des personnes sont éliminées. Au tour suivant une autre moitié etc (avec quelques byes possibles).

Finalement le gagnant est décidé dans le dernier et dernier tour.

Ceci peut être vu comme un arbre.

Chaque nœud de l'arbre sera le gagnant de la correspondance entre les enfants de ce nœud.

Les feuilles sont les joueurs. Le gagnant du premier tour sont les parents des feuilles, etc.

Ceci est un arbre binaire complet sur n nœuds.

Suivez maintenant le chemin du gagnant. Il y a des log n matches que le gagnant a joué. Considérez maintenant les perdants de ces correspondances log n. Le deuxième meilleur doit être le meilleur parmi ceux-là.

Le gagnant est décidé en n-1 matchs (vous en assommer un par match) et le gagnant parmi le logn est décidé en logn -1 matches. Ainsi, vous pouvez décider le plus grand et le second en n + logn-2.

En fait, il peut s'avérer que c'est optimal. Dans n'importe quel schéma de comparaison, dans le pire des cas, le gagnant devra jouer des matchs de logn.

Pour prouver que supposons un système de points où après un match, le gagnant obtient les points du perdant. Au départ, tous commencent avec 1 point chacun. A la fin, le vainqueur final a n points.

Maintenant donné n'importe quel algorithme, il pourrait être arrangé pour que le joueur avec plus de points soit toujours le gagnant. Puisque les points de n'importe quelle personne au plus doublent dans n'importe quel match dans ce scénario, vous avez besoin d'au moins n matches n joués par le gagnant dans le pire des cas.

Answer 2

Y at-il un problème avec cela? C'est au plus 3n comparaisons (sans compter la comparaison i < n). Si vous comptez cela, c'est 4n (ou 5n dans le second exemple).

double first = -1e300, second = -1e300; 
for (i = 0; i < n; i++){ 
    if (a[i] > first){ 
    second = first; 
    first = a[i]; 
    } 
    else if (a[i] > second && a[i] < first){ 
    second = a[i]; 
    } 
} 

une autre façon de coder:

for (i = 0; i < n; i++) if (a[i] > first) first = a[i]; 
for (i = 0; i < n; i++) if (a[i] < first && a[i] > second) second = a[i];