Trouver les éléments Max et 4th Max

Question

Pour trouver le maximum et le 4ème maximum d'un tableau, quel est le nombre minimum de comparaisons nécessaires? Je suppose que je dois utiliser un algorithme similaire à MinMax et la solution trouvée ici:

Find the 2nd largest element in an array with minimum number of comparisons \

Mais je ne sais pas comment j'adapter le style du tournoi à ce scénario.

Answer 1

Question intéressante ...

Je pense que le truc est juste pour lancer le tournoi une 2ème fois, mais avec le plus grand et 2ème retiré de l'ensemble (tel que déterminé par tournoi # 1).

Tournoi # 1: Pour trouver dans (1) [Le plus grand] et (2) [Le 2e]

Tournoi # 2: Avec (1) et (2) retiré de l'ensemble. Pour trouver dans (3) [Le plus grand] et dans (4) [Le 2ème plus grand]. Ceux-ci seront les 3ème et 4ème plus grands (respectivement) de l'ensemble original.

1. n - 1
2. log n - 1
3. (n-2) - 1
4. log (n-2) - 1

[Modifier]: Je ferais mieux Essayez quelques maths pour l'exhaustivité.

(1) + (2) + (3) + (4)

=> (n - 1) + (log n - 1) + ((n - 2) - 1) + (log (n-2) - 1)

=> 2n + (log n) + (log (n-2)) - 6

=> 2n + log (n^2 - 2n) - 6