Livre_silo 30 août 2013 16:32 Page 153
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
153
6 – Notions de complexité et algorithmique sur les tableaux
Comme on l’a vu au chapitre 3, les chaînes de caractères proposent les mêmes opérateurs
que les tableaux pour accéder à un caractère, connaître la longueur de la chaîne, extraire
une sous-chaîne, etc. La seule opération qui ne soit pas commune est la modification d’un
caractère, les chaînes étant immuables. Une conséquence appréciable est que certains des
programmes de ce chapitre sont utilisables sans changement sur des chaînes de caractères.
6.2.3 Parcours de tous les éléments d’un tableau
Pour exemple, on cherche à calculer la somme de tous les éléments d’un tableau d’entiers.
Un algorithme simple pour cela consiste à initialiser une variable s à 0 et à parcourir tous
les éléments du tableau pour les ajouter un par un à cette variable. La méthode naturelle pour effectuer ce parcours consiste à utiliser une boucle for. En effet, la construction
for i in range(n) affecte successivement à la variable i les valeurs 0, 1, . . ., n − 1. Ainsi
peut-on écrire la fonction somme de la manière suivante :
def somme(a):
s = 0
for i in range(len(a)):
s += a[i]
return s
Cependant, on peut faire encore plus simple, car la boucle for de Python sait parcourir
directement tous les éléments du tableau a avec for x in a . Ainsi, le programme se simplifie
en :
def somme(a):
s = 0
for x in a:
s += x
return s
Ce programme effectue exactement len(a) additions, soit une complexité linéaire.
Comme exemple plus complexe, on considère l’évaluation d’un polynôme :
A(X) =
∑
0⩽i
i
On suppose que les coefficients du polynôme A sont stockés dans un tableau a, le coefficient a i étant stocké dans a[i]. Ainsi, le tableau [1, 2, 3] représente le polynôme
3X
2 + 2X + 1. Une méthode simple, mais naïve, consiste à écrire une boucle qui réalise
exactement la somme telle qu’elle est écrite ci-dessus. On a donc besoin d’accéder non
seulement à l’indice i, mais aussi à la valeur a[i]. On peut parcourir le tableau en utilisant
la construction range, comme plus haut :
def evaluer(a, x):
s = 0
for i in range(len(a)):
s += a[i] * x**i
return s
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
153
6 – Notions de complexité et algorithmique sur les tableaux
Comme on l’a vu au chapitre 3, les chaînes de caractères proposent les mêmes opérateurs
que les tableaux pour accéder à un caractère, connaître la longueur de la chaîne, extraire
une sous-chaîne, etc. La seule opération qui ne soit pas commune est la modification d’un
caractère, les chaînes étant immuables. Une conséquence appréciable est que certains des
programmes de ce chapitre sont utilisables sans changement sur des chaînes de caractères.
6.2.3 Parcours de tous les éléments d’un tableau
Pour exemple, on cherche à calculer la somme de tous les éléments d’un tableau d’entiers.
Un algorithme simple pour cela consiste à initialiser une variable s à 0 et à parcourir tous
les éléments du tableau pour les ajouter un par un à cette variable. La méthode naturelle pour effectuer ce parcours consiste à utiliser une boucle for. En effet, la construction
for i in range(n) affecte successivement à la variable i les valeurs 0, 1, . . ., n − 1. Ainsi
peut-on écrire la fonction somme de la manière suivante :
def somme(a):
s = 0
for i in range(len(a)):
s += a[i]
return s
Cependant, on peut faire encore plus simple, car la boucle for de Python sait parcourir
directement tous les éléments du tableau a avec for x in a . Ainsi, le programme se simplifie
en :
def somme(a):
s = 0
for x in a:
s += x
return s
Ce programme effectue exactement len(a) additions, soit une complexité linéaire.
Comme exemple plus complexe, on considère l’évaluation d’un polynôme :
A(X) =
∑
0⩽i
i
On suppose que les coefficients du polynôme A sont stockés dans un tableau a, le coefficient a i étant stocké dans a[i]. Ainsi, le tableau [1, 2, 3] représente le polynôme
3X
2 + 2X + 1. Une méthode simple, mais naïve, consiste à écrire une boucle qui réalise
exactement la somme telle qu’elle est écrite ci-dessus. On a donc besoin d’accéder non
seulement à l’indice i, mais aussi à la valeur a[i]. On peut parcourir le tableau en utilisant
la construction range, comme plus haut :
def evaluer(a, x):
s = 0
for i in range(len(a)):
s += a[i] * x**i
return s