Complexité

Listes
Conclusion

Complexité d’un algorithme

Application aux listes

Alix Munier-Kordon et Maryse Pelletier

LIP6
Sorbonne Université
Paris

LU2IN003 Initiation à l’algorithmique

1
 Complexité
Listes
Conclusion

Plan du cours

1 Complexité
Introduction
Complexité d’un algorithme
Exemples de calculs de complexité
Méthodologie

2 Listes
Définition, représentation, primitives
Complexité

3 Conclusion

2
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Questions au sujet de l’évaluation d’un algorithme

1 Est-ce que l’algorithme résout le problème ?

terminaison
validité
2 Quelle est la complexité de l’algorithme ?
en temps de calcul
en taille mémoire
Objet de ce cours : la complexité en temps de calcul.

3
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Taille de codage des paramètres d’un algorithme

Definition
La taille de codage d’un paramètre est une évaluation, la plus
"raisonnable" possible, de la place nécessaire en mémoire pour
le stocker.
Quelle est la taille de codage d’un entier ? d’un tableau
d’entiers ?

4
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Complexité d’un algorithme

Definition
La complexité d’un algorithme est une évaluation du nombre
d’instructions élémentaires1 dans une exécution de
l’algorithme.

On l’exprime en fonction de la taille de codage des paramètres.

On en calcule un ordre de grandeur (notations de Landau).

1
Parfois on se concentre sur une instruction élémentaire représentative.
5
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Pire cas, meilleur cas

Complexité pire cas : on évalue le nombre d’instructions dans

le pire des cas (borne supérieure).
Complexité meilleur cas : on évalue le nombre d’instructions
dans le meilleur des cas (borne inférieure).
Exemple : recherche séquentielle d’un élément x dans un tableau T de taille n.
Instruction élémentaire représentative : comparaison.
Pire cas : x en dernière place de T ou pas présent → n comparaisons
Meilleur cas : x en première place de T → 1 comparaison

Par pessimisme, on identifie la complexité d’un algorithme avec

sa complexité dans le pire des cas.
La complexité de la recherche séquentielle est en O(n).

6
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Comparaison de complexités
Avec une durée de 10−6 secondes par instruction, on obtient les
durées suivantes (en secondes) pour n = 100

complexité durée
ln(n) 4, 60 × 10−6
n 10−4
n ln(n) 4, 60 × 10−4
n2 10−2
n3 1
2n ≈ 1, 27 × 1024
Remarque : 1, 27 × 1024 secondes ≈ 4 × 1016 ans !
Un algorithme de complexité logarithmique est meilleur qu’un
algorithme de complexité linéaire, meilleur qu’un algorithme de
complexité quadratique, etc.
Un algorithme de complexité exponentielle est à bannir.
7
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Somme des entiers

Pour n ∈ N, on veut calculer la somme Som(n) des entiers de 0

à n.
Autrement dit :
n
X
Som(n) = i
0

Cette somme vaut 0 si n = 0.

8
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Somme des entiers, en itératif

Algorithme itératif calculant la somme Som(n) :

def somIte(n):
res = 0
for i in range(1, n + 1):
res = res + i
return res

Complexité en nombre d’additions.

Soit c le nombre total d’additions et ci le nombre d’additions dans le tour de boucle i.
Alors ci = 1 pour tout i ∈ {1, . . . , n} et

n
X
c= ci = n
i=1

La complexité est en Θ(n), elle est linéaire.

9
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Somme des entiers, en récursif

Remarquons que Som(n) = Som(n − 1) + n si n > 0 et Som(0) = 0.
Algorithme récursif calculant la somme Som(n) :
def somRec(n):
if n == 0:
return 0
else:
return n + somRec(n - 1)
Complexité en nombre d’opérations : tests et additions.
Soit un le nombre d’opérations effectuées par l’appel somRec(n).
Alors un est la suite récurrente définie par :

un = un−1 + 2 si n > 0 et u0 = 0

Par substitution :

un = un−1 + 2 = un−2 + 4 = . . . = u0 + 2n = 2n + 1

La complexité est en Θ(n).

10
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Fibonacci, en itératif
Algorithme itératif calculant Fn :

def fibIte(n):
if (n == 0):
return 0
else:
x = 0 ; y = 1
for i in range(2, n + 1):
z = x + y ; x = y ; y = z
return y

Complexité en nombre d’additions.

Soit c le nombre total d’additions et ci le nombre d’additions dans le tour de boucle i.
Alors ci = 1 et
X n
c= ci = n − 1
i=2

La complexité en Θ(n).
Remarque : la complexité en nombre d’affectations est aussi linéaire.
11
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Fibonacci, en récursif

Algorithme récursif calculant Fn :

def fibRec(n):
if (n == 0) or (n == 1):
return n
else:
return fibRec(n - 1) + fibRec(n - 2)

Pour simplifier, on évalue la complexité en nombre d’additions.

Soit un le nombre d’additions effectuées par l’appel fibRec(n).
Alors un est la suite récurrente définie par :

un = un−1 + un−2 + 1 si n > 1 et u0 = u1 = 0

12
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Fibonacci, en récursif

un = un−1 + un−2 + 1 si n > 1 et u0 = u1 = 0

Theorem
un = Fn+1 − 1.
Preuve par récurrence.

Theorem
√
√1 (ϕn 1+ 5
Fn ≥ 5
− 1) où ϕ est le nombre d’or : ϕ = 2 ≈ 1, 618.

Preuve par récurrence.

La complexité est en Ω(ϕn ). Comme ϕ > 1, elle est exponentielle.
Elle croît très vite, par exemple : ϕ100 > 7, 9 ∗ 1020 .
13
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Calcul de la puissance : un premier algorithme

Algorithme basé sur la définition récursive naturelle de x n :

x n = x ∗ x n−1 si n > 0 et x 0 = 1

def puissSeq(x, n):

if (n == 0):
return 1
else:
return x * puissSeq(x, n - 1)

La complexité, en nombre de multiplications, est en Θ(n).

14
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Calcul de la puissance par dichotomie

On peut faire un calcul de x n par dichotomie :


 1 si n = 0
n n÷2 2
x = (x ) si n pair et n > 0
 n÷2 2
(x ) × x si n impair

où n ÷ 2 est le résultat de la division entière de n par 2.

15
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Calcul de la puissance par dichotomie : algorithme

Algorithme calculant x n par dichotomie :

def puissDicho(x, n):

if (n == 0):
return 1
else:
if n % 2 == 0:
return carre(puissDicho(x, n // 2))
else:
return carre(puissDicho(x, n // 2)) * x

où la fonction carre est ainsi définie :

def carre(x):
return x * x

16
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Calcul de la puissance par dichotomie : complexité

Soit un le nombre de multiplications effectuées par l’appel puissDicho(n).

 0 si n = 0
un = un÷2 + 1 si n pair et n > 0
un÷2 + 2 si n impair et n > 0


Dans tous les cas, pour n > 0, on a un ≤ un1 + 2 où n1 = n ÷ 2.

un ≤ un1 + 2 avec n1 = n ÷ 2
≤ un2 + 4 avec n2 = n1 ÷ 2 = n ÷ 22
≤ un3 + 6 avec n3 = n2 ÷ 2 = n ÷ 23
≤ ...
≤ unk + 2 ∗ k avec nk = n ÷ 2k

Les calculs s’arrêtent lorsque nk = 0, c’est-à-dire lorsque k = blog2 (n)c + 1.

Donc un ≤ 2 ∗ blog2 (n)c + 2.
La complexité est en O(log2 (n)), elle est logarithmique.

17
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Un peu de méthodologie

Complexité d’un algorithme itératif :

évaluer la complexité ci du tour de boucle i,
calculer la somme des ci pour tous les tours de boucle.
Exemples :
somIte(n) : ci = 1 pour i ∈ {1, . . . , n} et il y a n tours de
boucle
fibIte(n), pour n ≥ 2 : ci = 1 pour i ∈ {2, . . . , n} et il y a
n − 1 tours de boucle.

18
 Introduction
Complexité
Complexité d’un algorithme
Listes
Exemples de calculs de complexité
Conclusion
Méthodologie

Un peu de méthodologie

Complexité d’un algorithme récursif :

évaluer la complexité des cas de base,
établir une relation de récurrence permettant de calculer
cn . cn est exprimé en fonction des complexités des appels
récursifs et de la complexité b(n) des autres calculs.
Exemples :
somRec(n) : c0 = 1, cn = cn−1 + b(n) pour n > 0, avec
b(n) = 2
fibRec(n) : c0 = c1 = 0, cn = cn−1 + cn−2 + b(n) pour
n > 1, avec b(n) = 1
puissDicho(x, n) : c0 = 0, cn = cn÷2 + b(n) pour
n > 0, avec b(n) ≤ 2.

19
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Notion de liste

Definition
Une liste L = (a0 , · · · , an ) est une succession d’éléments.

jour=[’lundi’, ’mardi’, ’mercredi’]

corbeille=[56, ’jeudi’, 45, 67, ’coucou’]

Quels points communs (différences) voyez-vous entre listes et

ensembles ?
Definition
La liste L est homogène si tous ses éléments sont de même
type.

20
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Représentation des listes

Une liste peut être implémentée par :

un tableau,
une liste simplement chaînée,
une liste circulaire doublement chaînée.

21
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Primitives et opérations sur les listes

L[i] : renvoie l’élément en position i dans la liste L (positions

numérotées à partir de 0);
L[i : j] : renvoie la sous-liste de L composée des éléments situés entre
la position i et la position j − 1 comprises;
[Link](x) : insertion de l’élément x en queue de la liste L;
L. insert(i, x) : insertion de l’élement x en i-ème place;
L. pop(i) : renvoie l’élément en i-ème position et le supprime de la liste;
[Link](x) : détruit la première instance de l’élément x dans la liste L;
len(L) : renvoie le nombre d’éléments de L;
[Link](x) : indice du premier élément de valeur x dans L;
L. count(x) : nombre d’occurrences de x dans L;
L1 + L2 : renvoie la concaténation des deux listes;
L ? k : crée une liste de k occurrences de L.

22
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Complexité des primitives

Primitive Tableau Liste simpl. chaînée Liste doubl. circulaire

L[i] Θ(1) Θ(i) Θ(i)
[Link](x) O(n) Θ(n) Θ(1)
[Link](i,x) Θ(n − i) Θ(i) Θ(i)
[Link](i) Θ(n − i) Θ(i) Θ(i)
[Link](x) Θ(n) O(n) O(n)
[Link](x) O(n) O(n) O(n)
[Link](x) Θ(n) Θ(n) Θ(n)
L1 + L2 O(n1 + n2 ) Θ(n1 ) Θ(1)
L?k Θ(n × k ) Θ(n × k ) Θ(n × k )
len(L) Θ(1) Θ(n) Θ(n)
n = |L|, n1 = |L1 |, et n2 = |L2 |.

23
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Exemple : fonction miroir

def swapp (tab, i, j):

aux = tab[i]; tab[i]=tab[j]; tab[j]=aux

def miroir(tab):
n = len(tab)
i = 0 ; j = n -1
while i < j:
swapp(tab, i, j)
i = i + 1; j = j - 1

24
 Complexité
Définition, représentation, primitives
Listes
Complexité
Conclusion

Complexité de miroir en fonction de la représentation

de tab

len(tab) swapp(tab, i, j) miroir (tab)

Tableau Θ(1) Θ(1) Θ(n)
Liste simpl. chaînée Θ(n) Θ(max(i, j)) Θ(n2 )
Liste doubl. circulaire Θ(n) Θ(max(i, j)) Θ(n2 )
n = |tab|.

25
 Complexité
Listes
Conclusion

Conclusion
Sur la complexité
Un même problème peut être résolu par différents algorithmes.
Il est important de connaître un ordre de grandeur de la
complexité de chaque algorithme.
Il faut proscrire les algorithmes de complexité exponentielle.
Sur les listes
Plusieurs représentations possibles des listes avec des
primitives d’accès et de gestion de complexité différentes.
Quand on évalue la complexité d’un algorithme, il faut connaître
précisement la complexité de toutes les primitives associées aux
structures de données.
Choisir la structure de données en fonction des traitements à
réaliser.
26