On suppose que l'on a une liste L, de longueur n = len(L) > 0, de nombres.
Écrire une fonction moyenne qui
$$m = \frac{1}{n} \sum_{i=0}^{n-1} \text{L}[i]$$
On peut d'abord écrire une réponse sous forme d'un algorithme en pseudo-code.
FONCTION moyenne
ENTRÉE: liste L de nombres
SORTIE: moyenne des items de de L
DÉBUT
initialiser un accumulateur à 0
POUR CHAQUE item de L FAIRE
ajouter item à l'accumulateur
FIN
calculer accumulateur / nombre d'items de L
RENVOYER le résultat
FIN
Ce qui traduit en Python devient :
def moyenne(L):
acc = 0
for item in L:
acc += item # raccourci équivalent à acc = acc + item
m = acc / len(L)
return m
Si on exécute ce programme, il ne se passe rien. On s'est contenté de définir la fonction moyenne mais celle-ci n'est jamais explicitement appelée !
Pour le test, on pourrait – après exécution – écrire en console
>>> moyenne([4, 12, 9, 7, 6]) 7.6
On peut aussi ajouter à la suite du programme :
m = moyenne([4, 12, 9, 7, 6]) print(m)
Vous pouvez d'ailleurs visualiser l'exécution de ce programme sur Python tutor.
Préciser le nombre d’opérations (additions et division) nécessaires pour faire ce calcul en fonction de la taille de L – c'est à dire le nombre d'élément de L, soit encore n = len(L).
def moyenne(L):
acc = 0 # 1 fois
for item in L: # n fois
acc += item # n fois
m = acc / len(L) # 1 fois
return m # 1 fois
Certaines lignes sont exécutées une seule fois, d'autres sont exécutées plusieurs fois : n fois avec n étant le nombre d'items de L.
Python étant un langage de haut niveau, il fait beaucoup de choses cachées pour nous faciliter la vie. Il est donc difficile de savoir si toutes les lignes s'exécutent à la même vitesse. Par exemple, en ligne 5, le calcul acc / len(L) est plus compliqué qu'il y parait : d'abord il faut calculer len(L). Combien de temps cela prend-il ?
Pour raisonner, on va néanmoins faire comme si toutes les lignes avaient la même durée d'exécution. Nous avons donc ici 2n + 4 lignes exécutées.
Mais, comme on a été obligé de faire une grosse hypothèse, on n'est pas totalement sûr que ce ne soit pas plutôt 3n + 2 ou 2n + 7 ou… C'est pourquoi, ce qui est surtout important, c'est la forme du résultat. Ici c'est une fonction affine en n. On a un coût linéaire.
On rappelle que la variance de la liste L considérée comme une série statistique est la moyenne des carrés des écarts à la moyenne, c’est-à-dire – 2 formules équivalentes :
$$V = \frac{1}{n} \sum_{i=0}^{n-1} (\text{L}[i] - m)^2 = \frac{1}{n}\left(\sum_{i=0}^{n-1} \text{L}[i]^2 \right) - m^2$$
En supposant que la fonction moyenne est déjà écrite donc utilisable, écrire deux fonctions variance1 et variance2 qui pour une liste de nombres retourne sa variance en utilisant chacune des deux caractérisations de la variance données ci-dessus.
Dans la fonction moyenne, nous avons traduit $\sum_{i=0}^{n-1} \text{L}[i]$ par la boucle for. Il suffit d'adapter le calcul pour la première formule de variance :
def variance1(L):
acc = 0
m = moyenne(L)
for item in L:
acc += (item - m)**2
v = acc / len(L)
return v
Dans la deuxième formule, il faut $\sum_{i=0}^{n-1} \text{L}[i]^2$, l'adaptation est là aussi rapide :
def variance2(L):
acc = 0
for item in L:
acc += item**2
v = acc / len(L) - moyenne(L)**2
return v
méthode plus élégante mais plus difficile
La variance peut être vue comme la moyenne des carrés des éléments de L moins la moyenne de L au carré. Si on veut calculer la moyenne des carrés des éléments de L, il faut produire une liste contenant les carrés des éléments de L et prendre leur moyenne. On a alors :
# autre version possible
def variance(L):
return moyenne([item**2 for item in L]) - moyenne(L)**2
Préciser le nombre d’opérations élémentaires nécessaires pour une liste de longueur n pour chacune des deux fonctions
Je ne reprends que le cas de variance1 :
def variance1(L):
acc = 0 # 1
m = moyenne(L) # 2n + 3 (vu avant)
for item in L: # n
acc += (item - m)**2 # n
v = acc / len(L) # 1
return v # 1
Le coût est donc en 4n +6, soit un coût linéaire.
Pour calculer la variance avec cette formule, on a besoin de calculer moyenne(L). On pourrait imaginer de faire ceci :
def variance1(L):
acc = 0
for item in L:
acc += (item - moyenne(L))**2 # on recalcule n fois la moyenne !
v = acc / len(L)
return v
Comme vous le voyez, la moyenne est recalculée n fois et comme chaque calcul de moyenne coûte 2 n + 3, cela nous donne un coût en n(2n +3) donc un coût en n². C'est beaucoup moins bien ! Il est donc utile de bien organiser ses calculs pour éviter de recalculer sans cesse la même chose et de perdre du temps.