Recherche des plus grand et petit éléments dans un tableau
L’objectif de ce document est d’écrire et d’implémenter un algorithme s’appuyant sur le raisonnement « Diviser pour régner » qui permet de déterminer le maximum et le minimum des éléments dans un tableau.
-
Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.
-
Utiliser les fonctions
minetmaxfournies par le langage Python afin d’afficher les maximum et minimum dans la liste. -
Écrire le code de la fonction
maxmin1qui, à partir d’un algorithme de « brute force », détermine les maximum et minimum dans la liste passée en argument. La spécification de la fonction est :
-
Vérifier le bon fonctionnement de la fonction
maxmin1en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python. -
Quelle est la complexité de la fonction
maxmin1? -
Comparer l’efficacité de la fonction
maxmin1à celle des fonctions fournies par Python en mesurant les durées d’exécution à l’aide de la fonctiontimedu moduletime. -
En faisant varier le nombre d’éléments dans le tableau, vérifier si les durées d’exécution de la fonction
maxmin1correspond bien à la complexité établie à la question 5. La complexité des fonctionsmaxetminfournies par Python vous semblent-elles être en ? -
Écrire et implémenter la fonction
maxmin2qui implémente le raisonnement «Diviser pour régner » pour résoudre ce problème. Dans un premier temps, écrire une fonction qui se contente de déterminer le maximum dans la liste passée en argument. Compléter ensuite le code de façon à ce que le maximum et le minimum soient retournés. La spécification de la fonction est :
-
Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.
-
Modifier la fonction
maxmin2afin qu’elle retourne les maximum et minimum dans la liste. La spécification de la fonction est :
-
Quelle est la complexité de cette fonction ?
-
Vérifier le bon fonctionnement de la fonction à la suite des précédentes vérifications.
-
La fonction
maxmin2est-elle, théoriquement, plus efficace que la fonctionmaxmin1? Dans la pratique ? Comment expliquer ce comportement ?