Comprendre une trace d'exécution pour analyser un code et son coût
Dérouler à la main la trace d'exécution d'un programme Python (variables, tests, itérations), en déduire sa fonction et le nombre d'opérations pour estimer sa complexité.

Les points essentiels
- Une trace d'exécution est un tableau qui note, après chaque instruction ou à chaque tour de boucle, la valeur de toutes les variables concernées : elle rend visible ce que le programme fait réellement.
- Pour tracer un programme, on part de l'état initial des variables, on exécute les instructions dans l'ordre exact du code et on recopie l'état obtenu à chaque étape, sans deviner le résultat.
Les mots à connaître
- Trace d'exécution
- Tableau, construit à la main ou par un outil, qui liste l'évolution des valeurs des variables au fil des instructions ou des itérations d'un programme sur une entrée donnée.
- Complexité (en temps)
- Ordre de grandeur du nombre d'opérations élémentaires effectuées par un algorithme en fonction de la taille n de son entrée, par exemple linéaire (proportionnel à n) ou quadratique (proportionnel à n²).
Un exemple pour comprendre
On considère : def f(t): m = t[0] ; for x in t: if x > m: m = x ; return m. Écrire la trace pour t = [3, 8, 2, 8, 5], dire ce que calcule f et estimer sa complexité.
État initial : m = 3. Itérations : x=3, 3>3 faux, m=3 ; x=8, 8>3 vrai, m=8 ; x=2, 2>8 faux, m=8 ; x=8, 8>8 faux, m=8 ; x=5, 5>8 faux, m=8. La fonction renvoie 8. La trace montre que m ne fait que croître et vaut toujours le maximum des éléments déjà lus (invariant) : f renvoie le plus grand élément de la liste. Le test de égalité 8>8 est faux, donc m n'est pas modifié inutilement. Il y a 5 tours pour 5 éléments : pour une liste de taille n, n comparaisons, donc une complexité linéaire, de l'ordre de n.

