Extrema et moyenne d'une liste
Extrema et moyenne d'une liste
Extrema et moyennes d’une liste
Il s’agit ici de traiter des premiers algorithmes au moyen de la recherche d’extrema et de moyennes d’une liste.
On commence par définir une liste non classée $L = [2, 1, 3, 5, 4, 2, 6, 3]$. On souhaite déterminer le maximum de la liste :
def maximum(L): maxi = L[0] for i in L: if i > maxi : maxi = i return maxi
Pour comprendre le fonctionnement de l’algorithme, une méthode consiste à appliquer à la main les instructions de ce dernier.
Lors de la première instruction $i$ n’existe pas encore et maxi vaut $2$. $i$ prend alors la première valeur de la liste. Or, $2$ n’est pas strictement plus grand que $2$, maxi ne change donc pas. $i$ prend ensuite la valeur $1$. Or $1$ n’est pas plus grand que $2$ donc maxi ne change pas. $i$ prend alors la valeur $3$ et $3 > 2$ donc maxi prend comme nouvelle valeur $3$ et ainsi de suite.
On regroupe la valeur des différentes variables dans le tableau suivant.
| $i$ | $varnothing $ | 2 | 1 | 3 | 5 | 4 | 2 | 6 | 3 |
| maxi | 2 | 2 | 2 | 3 | 5 | 5 | 5 | 6 | 6 |
En changeant le signe $>$ en $<$ on peut alors déterminer le minimum d’une liste.
On s’intéresse ensuite à la notion de complexité temporelle d’un algorithme qui correspond au nombre d’opérations élémentaires effectués par l’algorithme. Une opération élémentaire peut être une comparaison, une affectation ou une opération arithmétique (somme ou produit). On essaie ainsi d’estimer, pour de grandes valeurs de $n$, le temps nécessaire à l’ordinateur pour traiter le problème.
On s’intéresse davantage aux grandes valeurs de $n$ car on suppose que les ordinateurs traitent des listes avec un grand nombre de données et on peut supposer que $n$ tend vers l’infini.
On commence par supposer que la taille de la liste $L$ est $n$. Les instructions dans la boucle for sont effectuées $n$ fois. Il y a donc $n$ comparaisons. La difficulté est dans l’estimation des autres paramètres. En effet, le nombre d’affectations dépend du choix de la liste. La stratégie consiste alors à déterminer le meilleur des cas (celui qui minimise le nombre d’affectations) et le pire des cas (le plus couteux pour l’ordinateur). Ici, le meilleur des cas est le cas pour lequel le maximum de la liste est situé en première position.
Il y a donc une seule affectation : celle de la première ligne car la condition ne supériorité ne sera jamais réalisée. Dans le pire des cas, il y a $n$ affectations (si le maximum est en fin de liste et que la liste est triée dans l’ordre croissant). Ainsi, la complexité varie entre $n+1$ et $2n$, c’est à dire le produit d’une constante par $n$ (car pour de grandes valeurs de $n$ c’est le terme en $n$ qui domine) : on parle d’une complexité linéaire.
D’autres algorithmes élémentaires peuvent être appliqués à une liste.
On peut par exemple calculer la somme des éléments d’une liste. def som(L): somme = 0 for i in L: somme = somme + i return somme
Le réflexe est à présent de calculer la complexité du programme ainsi établi.
Tout d’abord, le nombre de tests est nul.
Ensuite, il y a $n$ affectations dans la boucle for et une affectation sur la première ligne, soit $n + 1$ affectations.
De plus, il y a $n$ sommes (opérations arithmétiques).
Au total, on peut ici parfaitement déterminer le nombre d’opérations élémentaires : il y en a $2n +1$. Ainsi, pour de grandes valeurs de $n$ on dit que la complexité est de $2n$ soit une complexité linéaire que l’on note $mathcal{O}(n)$ (grand O de $n$).
Enfin, on donne comme dernier exemple un algorithme permettant de calculer la moyenne d’une liste.def moy(L): moyenne = 0 for i in L: moyenne = moyenne + i moyenne = moyenne /len(L) return moyenne
La fonction len(L) permet de calculer la taille de la liste L.
On étudie à nouveau la complexité de l’algorithme pour une liste de taille $n$.
Tout d’abord, il n’y a pas de comparaisons. Ensuite, il y a $n + 2$ comparaisons et $n+1$ opérations arithmétiques. Ainsi, la complexité vaut $2n + 3$, c’est à dire une complexité en $mathcal{O}(n)$.
En conclusion, il existe des algorithmes plus rapides que les algorithmes linéaires (on parle alors d’algorithme sous-linéaire, de complexité en $k log(n)$ avec $log$ la fonction logarithme).
A l’inverse, d’autres algorithmes sont plus lents (en $k n^2$ par exemple).
Enfin, il existe des algorithmes à temps exponentiel pour lesquels, lorsque la taille de la liste augmente, le temps nécessaire devient très rapidement extrêmement grand. On retiendra qu’on essaie d’économiser le temps au maximum et que trouver les algorithmes les plus adaptés est l’un des objets d’étude de l’algorithmique.