Lycée > Premiere > NSI > Algorithmes de recherche : obtenir une moyenne, une médiane

Algorithmes de recherche : obtenir une moyenne, une médiane

Fiche de cours
Quiz
Profs en ligne
Videos
Application mobile

Objectifs

Écrire un algorithme de calcul de la moyenne des éléments d’un tableau.
Écrire un algorithme de recherche de la médiane des éléments d’un tableau.

Points clés

Le cout d’un calcul de moyenne d’un tableau est linéaire en n la taille du tableau.
Il est nécessaire de trier un tableau pour en déterminer la médiane. On utilise soit la méthode sort(), soit la fonction sorted().
Un tableau est indexé à partir de 0. Le i-ème élément a pour indice i−1.

Pour bien comprendre

Algorithmes de recherche : parcourir un tableau

1. Obtenir une moyenne

a. Algorithme

La moyenne d’un tableau de nombres entiers et/ou flottants est égale à la somme des éléments du tableau divisée par l’effectif total.

Voici ci-dessous un algorithme qui détermine la moyenne des éléments d’un tableau Tab (non vide et non trié) de taille n.

S ← 0	0 est affecté à la variable S.
Pour i allant de 0 à n−1	i = 0, puis i = 1, puis i = 2, puis… i = n − 1.
S ← S + Tab[i]	La somme de l’ancienne valeur de S et de Tab[i] est affectée à S.
FinPour	Fin de l’instruction « Pour ». S contient alors la somme des éléments de Tab.
Retourner S/n	La moyenne S/n est retournée à la fin.

b. Programmation en Python

En Python, la fonction moyenne(Tab) implémente un algorithme de calcul de la moyenne de Tab.

def moyenne(Tab):	On définit la fonction moyenne.
S = 0	0 est affecté à la variable S.
for elt in Tab:	Pour chaque élément elt de Tab,
S = S + elt	on ajoute elt à S.
return S/len(Tab)	On retourne la variable S/len(Tab) (somme sur longueur de la table).

c. Cout

L’algorithme de la sous-partie précédente, appliqué à un tableau comportant n éléments, nécessite :

n + 1 affectations : une affectation avant l’instruction pour et n affectations pendant celle-ci.
n + 1 opérations : n additions dans l’instruction pour et une division.

Si le cout d’une affectation et celui d’une opération sont respectivement notés a et op, alors le cout de l’algorithme est égal à :

a × (n + 1) + op × (n + 1) = (a + op)n + (a + op)
(car a × (n + 1) + op × (n + 1) = a × n + a + op × n + op).

On obtient une fonction affine en n. On dit alors que le cout d’un algorithme de calcul de la moyenne d’un tableau est linéaire en n la taille du tableau.

À retenir
Le cout d’un calcul de moyenne d’un tableau non trié est linéaire.

2. Obtenir une médiane

a. Algorithme

La médiane d’une série statistique est une valeur telle que 50 % des valeurs de la série lui sont inférieures ou égales, et 50 % des valeurs de la série lui sont supérieures ou égales. En pratique, il faut trier dans l’ordre croissant la série.

Il y a ensuite deux cas, suivant la parité de l’effectif n de la série.

Si n est impair, il y a une seule valeur centrale. La médiane est la -ième valeur de la série triée.
Si n est pair, il y a deux valeurs centrales. La médiane est la moyenne de la -ième et de la -ième valeur de la série triée.

Voici ci-dessous un algorithme qui détermine la médiane des éléments d’un tableau Tab (non vide et non trié) de taille n.

Trier Tab	On obtient un tableau Tab d’éléments triés dans l’ordre croissant.
Si n%2 = 0, alors	Si n est pair, alors
med ← (Tab[n/2 − 1] + Tab[n/2])/2	on affecte à med la moyenne des deux valeurs centrales,
Sinon	sinon (c’est-à-dire si n est impair),
med ← Tab[(n−1)/2]	on affecte à med la valeur centrale.
FinSi	Fin de l’instruction conditionnelle.
Retourner med	La médiane med est retournée à la fin.

Remarque
Il faut faire attention aux indices. Comme les tableaux sont indexés à partir de 0, la

-ième valeur est Tab[n/2 − 1] et la

-ième valeur est Tab[n/2].

Exemple
Si Tab = [7,8,9,10,11], alors n = 5 et la médiane est Tab[2]. On obtient l’indice 2 en calculant

(

b. Programmation en Python

En Python, deux fonctions existent pour trier des tableaux : sort et sorted. Elles sont toutefois très différentes.

Si on considère le tableau Tab, alors Tab.sort() trie Tab en place, aucun autre tableau n’est créé. En revanche, sorted(Tab) crée un nouveau tableau, Tab reste inchangé.

Remarque
Une variable créée est stockée dans une partie du disque dur de l’ordinateur. Le terme « en place » signifie que le tableau trié occupe le même espace mémoire que le tableau d’origine. Cela rend l’exécution plus rapide. Aucun autre espace mémoire n’est alloué.

Exemple
Dans la console de Python, on a les tris suivants selon la méthode utilisée.

avec sort()	avec sorted()
>>> Tab = [1, 3, 4, 2, 5] >>> Tab [1, 3, 4, 2, 5] >>> Tab.sort() >>> Tab [1, 2, 3, 4, 5]	>>> Tab = [1, 3, 4, 2, 5] >>> sorted(Tab) [1, 2, 3, 4, 5] >>> Tab [1, 3, 4, 2, 5]

En Python, la fonction mediane(Tab) implémente un algorithme de calcul de la médiane de Tab.

def mediane(Tab):	On définit la fonction médiane.
Tab.sort()	On trie le tableau Tab.
n = len(Tab)	On affecte à n la longueur de Tab.
if n%2 == 0:	Si n est pair, alors
return (Tab[n//2-1] + Tab[n//2])/2	on retourne la moyenne des deux valeurs centrales.
else:	Sinon (si n est impair),
return Tab[(n-1)//2]	on retourne la valeur centrale.

Remarque
En Python, // renvoie un entier et / renvoie un flottant (8//2 renvoie 4 alors que 8/2 renvoie 4.0).
Pour accéder aux éléments du tableau, on utilise la division entière // et non la division décimale / car les indices des tableaux doivent être des entiers (de type int).

c. Cout

Il n’est pas possible de déterminer le cout de l’algorithme de la sous-partie précédente puisque l’on ne connait pas le cout d’un tri de tableau.

En général, le cout d’un algorithme n’est pas étudié si on utilise des fonctions pré-implémentées (ici la fonction médiane) dans le langage utilisé.