Sélectionnez, parmi les réponses proposées, celles qui peuvent influer sur le temps d'exécution d'un programme mettant en oeuvre un algorithme.

Le temps d’exécution d’un même programme sur les mêmes données et exécuté sur une même machine peut-il varier d’une exécution à l’autre ? Pourquoi ?

Pour mesurer expérimentalement le temps d'exécution d'un programme, on peut suivre la procédure suivante :

1. Exécuter le programme pour plusieurs instances du problème
2. Mesurer le temps pris par chaque exécution

Toutefois, cette procédure ne permettra pas d'estimer de façon fiable la complexité temporelle de l'algorithme une fois implémenté. Sélectionnez, parmi les réponses proposées, celles qui permettent d'améliorer la procédure proposée pour réaliser une estimation plus fiable de la complexité temporelle.

Réalisez maintenant l'étude expérimentale sur l'implémentation produite dans l'exercice précédent. Pour ce faire, commencez par suivre la référence sur l'étude expérimentale disponible sur Moodle. On vous demande de réaliser l'ensemble des étapes, de la génération aléatoire d'instances à la production d'un graphe illustrant vos résultats. Comparez vos résultats avec les complexités calculées lors de l'exercice précédent.

On vous demande de produire le graphe de la complexité, mesurée expérimentalement, des deux implémentations que vous avez réalisées.

Concernant le graphe :

• Pensez à définir un titre
• Pensez à définir les axes du graphe (les unités si il y en a)
• Faites attention à l'échelle utilisée pour représenter les axes (linéaire, logarithmique,..)
• Utilisez des barres d'erreur pour identifier la variabilité des résultats

Prenez un peu de recul sur votre graphe :

• Avez-vous obtenu des résultats clairs ? Si ce n'est pas le cas, discutez-en avec votre tuteur.
• Comparez la complexité, mesurée expérimentalement, des implémentations efficace et simple (fournie en pseudo-code). Pouvez-vous observer une différence entre les complexités expérimentales des deux implémentations que vous avez produites ?
• Pouvez-vous identifier des meilleurs et pire cas ? Comment les représenteriez-vous sur vos graphes ?

Supposons que votre étude expérimentale vous mène au graphe suivant. Ce graphe indique le temps d'exécution en fonction de la taille des instances :

Que pouvez-vous dire à propos de la complexité temporelle de la fonction ? Supposez que n correspond à la taille des instances.