Recherche de maximum
Cet algorithme sert à chercher l'indice d'un élément maximal d'un tableau non vide. C'est une recherche linéaire, qui parcourt chaque case du tableau et garde en mémoire l'indice du plus grand élément vu parmis ceux vus.Pseudo-code
Entrée: T un tableau de n élémentsSortie: i tel que T[i] est le plus grand élément de T
Principe
L'indice i_max du pseudo-code correspond à chaque étape à l'indice du plus grand élément entre 0 et i. Lorsque i augmente, i_max est mis à jour si T[i] > T[i_max].Terminaison et complexité
Cet algorithme effectue au pire n tours de la boucle while car la boucle s'arrête lorsque i dépasse n, et i commence à 0 et croît strictement à chaque passage. La complexité totale de l'algorithme est donc de O(n) .Correction
A chaque passage sur la ligne 2, la condition suivante est vérifiée:
"T[i_max] est le plus grand élément parmis T[0], .. T[i-1]."
A la fin de l'exécution, i vaut n, et l'invariant devient: "T[i_max] est le plus grand élément parmis T[0], .. T[n-1]."
Autrement dit, i_max est l'indice du plus grand élément de T.
A la fin de l'exécution, i vaut n, et l'invariant devient: "T[i_max] est le plus grand élément parmis T[0], .. T[n-1]."
Autrement dit, i_max est l'indice du plus grand élément de T.