Bonjour,
 
Je n'arrive pas à trouver l'algorithme permettant de trouver les deux plus grands éléments d'une liste à l'aide de la méthode du tournoi...tout en ayant une complexité d'ordre n, ou logarithmique...
 
Je vois le principe des arbres où le premier plus grand élément est trouvé au premier tour, et le second plus grand élément est trouvé dés le deuxieme parcours (on aura conservé les perdants face au plus grand élémént du premier tour)...
 
mais je n'arrive pas àmettre en oeuvre.
 
Si quelqu'un a l'algorithme sous la main...  

Le plus simple si ta liste n'est pas trie est en complexite O(n) et c'est comme une recherche de max sauf que tu as deux variables au lieux d'une.
Si ta liste est triee alors tu peux avoir une recherche dichotomique: O(log(n)) toujours avec deux variables...

Salut
 
je viens de mettre en oeuvre la méthode en C, l'algo fonctionne bien, mais on doit pouvoir faire sans doute mieux.
 
On suppose qu'on a un tableau T du style
________________________________________
|  5 |  1 | 10 |  3 | 15 | 19 |  5 |  8 | 20 | 30 |
________________________________________
   0     1     2    3     4     5     6    7    8     9
 
On va construire une suite de tableaux de ce style
 
T1
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
 
On mémorise 0 car T[0] est plus grand que T[1].
On mémorise 2 car T[2] est plus grand que T[3].
On mémorise 5 car T[5] est plus grand que T[6].
 
 
T2
___________
|  2 | 5 | 9 |  
___________
 
On mémorise 2 car T[T1[1]] est plus grand que T[T1[0]].
On mémorise 5 car T[T1[2]] est plus grand que T[T1[3]].
On mémorise 9 car T[T1[4]] est seul.
 
 
T3
________
|  5 | 9 |  
________
 
On mémorise 5 car T[T2[1]] est plus grand que T[T1[0]].
On mémorise 9 car T[T2[3]] est seul.
 
T4
____
|  9 |  
____
On a terminé, T[T4[0]] est le plus grand nombre.
 
Pour pouvoir trouver le second plus grand élément, il faut parcourir la liste des tableaux en sens inverse
J'ai donc créer une structure où je mémorise la place de chaque nombre dans le tableaux précédent.
Mes tableaux T1, T2, et T3 se présentent sous cette forme :
   
T1
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
|  0 |  2 | 5 |  7 | 9 |  
__________________
 
 
T2
___________
|  2 | 5 | 9 |  
___________
|  1 | 3 | 4 |  
___________
 
T3
________
|  5 | 9 |  
________
|  1 | 2 |  
________
 
 
T4
____
|  9 |  
____
|  1 |  
____
 
 
Enfin il faut faire attention aux limites de tableaux, donc il faut mémoriser dans un tableaux à part la taille de chaque tableau intermédiaire.

Au lieu de s'en tenir au système de l'arbre et du parcours en arrière, en réfléchissant un peu, on peut trouver les deux nombres en même temps : en effet, on mémorisera en même temps le plus grand des nombres à comparer et le plus grand de ceux qu'il aura "dominés".
 
 
On suppose qu'on a un tableau T du style  
___________________________________________
|  5 |  1 | 10 |  3 | 15 | 19 |  5 |  8 | 20 | 4 |30 |  
___________________________________________  
 
 
On va construire une suite de tableaux de ce style  
 
T1  
_________________________
|  5 | 10 |  19 |  8 | 20 | 30 |
_________________________
|  1 |   3 | 15 |  5 |  4 |  MIN_INT
_________________________
 
C'est - à - dire qu'on mémorise le plus grand et l'autre au premier tour.
S'il reste un nombre tout seul, on peut utiliser INT_MIN en plus petit en C.
 
 
T2  
_____________
| 10 | 19 | 30 |  
_____________
|  5 | 15 | 20 |
_____________
 
Cette fois-ci on mémorise 10 car il est plus grand que 5 et comme 5 est plus grand que 3, on mémorise en second plus grand 5
On mémorisera enxsuite 19 car il est plus grand que 8 et on garde 15.
Enfin on mémorise 30 et 20 en plus petit
 
T3  
_________
| 19 | 30 |  
_________
| 15 | 20 |
__________
 
On garde (19, 15) et (30,20)
 
T4  
_____
| 30 |  
_____  
| 20 |
_____
On a terminé, 30 et 20 sont bien les deux plus grands nombres !