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.

  1. Générer une liste contenant un million de termes choisis aléatoirement entre un et mille milliards.

Réponse
1
2
3
4
from random import randint

if __name__ == "__main__":
    tab = [randint(1, int(1e12)) for i in range(int(1e6))]

  1. Utiliser les fonctions min et max fournies par le langage Python afin d’afficher les maximum et minimum dans la liste.

Réponse
1
2
3
4
    print("Fonctions Python")
    val_min, val_max = (min(tab), max(tab))

    print("min = {}, max = {}".format(val_min, val_max))

  1. Écrire le code de la fonction maxmin1 qui, à 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 :
1
2
3
4
5
6
def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """

Réponse
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def maxmin1(tab: List[float]) -> Tuple[float, float]:
    """
    Recherche du minimum et du maximum dans le tableau tab.

    Paradigme « Brute force »
    """
    val_max = tab[0]
    val_min = tab[0]

    for elt in tab:
        if elt > val_max:
            val_max = elt
        if elt < val_min:
            val_min = elt

    return (val_min, val_max)

  1. Vérifier le bon fonctionnement de la fonction maxmin1 en affichant les maximum et minimum dans la liste, à la suite de ceux déterminés à l’aide des fonctions fournies par Python.

Réponse
1
2
3
    print("Recherche « Brute Force »")
    val_min, val_max = maxmin1(tab)
    print("min = {}, max = {}".format(val_min, val_max))

  1. Quelle est la complexité de la fonction maxmin1 ?

Réponse

Il est nécessaire de parcourir tout le tableau, la complexité est donc en $O(N)$.

[Lire]