Informatique 2

Algorithmique 2/Python
Chapitre 4: Complexité algorithmique

1
Objectifs du cours

❑ Comprendre et utiliser des fonctions et des procédures en Python.

❑ Appliquer la récursivité pour résoudre des problèmes spécifiques.

❑ Introduire la notion d’enregistrement et manipuler les fichiers en

Python pour lire, écrire et modifier des données.

❑ Calculer la complexité d'un algorithme.

2
Organisation du cours

Chapitre 1: Introduction et Rappels sur l’algorithmique en

Python

Chapitre 2: Fonctions, Procédures et Récursivité

Chapitre 3: Enregistrements et Fichiers

Chapitre 4: Complexité algorithmique

3
Plan du chapitre
❑Introduction et définitions

❑Calcul de la complexité temporelle

❑Calcul de complexité de quelques opérations sur les

listes

4
Introduction et définitions

5
Introduction
• Exercice

• Ecrire en python une fonction qui prend en argument une chaîne de

caractères et détermine si le caractère 'a' est présent dans la chaîne
(on retourne soit 𝑇𝑟𝑢𝑒 soit 𝐹𝑎𝑙𝑠𝑒).

6
Introduction
• Plusieurs Solutions possibles

7
Introduction
• Exercice
• Ecrire en python une fonction qui prend en argument une chaîne de
caractères et détermine si le caractère 'a' est présent dans la chaîne (on
retourne soit 𝑇𝑟𝑢𝑒 soit 𝐹𝑎𝑙𝑠𝑒).

• Plusieurs Solutions possibles

• Quelques questions :
1. Que remarquez vous concernant cet exercice ?

2. Le code le plus court ! Est-il meilleur ?

3. Comment peut-on désigner le meilleur code parmi ces quatre solutions ?

8
Pourquoi calculer la complexité d’un algorithme
• La complexité algorithmique est une sorte de quantification de la performance
d'un algorithme.

• L'objectif premier d'un calcul de complexité algorithmique est de pouvoir

comparer l’efficacité d’algorithmes résolvant le même problème. Dans une
situation donnée, cela permet donc d'établir lequel des algorithmes disponibles
est le plus optimal.

• Ce type de question est primordial, car pour des données volumineuses la

différence entre les durées d'exécution de deux algorithmes ayant la même
finalité peut être de l'ordre de plusieurs jours.
9
Définition de la complexité d’un algorithme
• Définition
• La complexité d'un problème algorithmique 𝑃 est une mesure de la quantité de
ressources nécessaires à la résolution du problème 𝑃.

• Cette mesure est basée sur une estimation du nombre d'opérations de base
effectuées par l'algorithme en fonction de la taille des données en entrée de
l'algorithme.

• Généralement, pour le même problème 𝑃, on peut trouver plusieurs

algorithmes(𝐴𝑙𝑔1; 𝐴𝑙𝑔2; . . ; 𝐴𝑙𝑔𝑛).

• L'objectif de la complexité est d’évaluer le coût d'exécution de chaque algorithme

afin de choisir le meilleur.
10
Types de complexité d’un algorithme
• Le calcul de la complexité d’un algorithme permet de mesurer sa
performance. Il existe deux types de complexité :
1. Complexité temporelle : permet de quantifier la vitesse d’exécution

2. Complexité spatiale : permet de quantifier l’utilisation de la mémoire

• Remarque:
• Le coût de la mémoire étant aujourd’hui relativement faible, on cherche en
général à améliorer la complexité en temps plutôt que la complexité en
mémoire.

• Dans ce cours, on s’intéresse à la complexité temporelle.

11
Calcul de la complexité
temporelle

12
Complexité temporelle d’un algorithme
• Définition:
• Réaliser un calcul de complexité en temps revient à compter le nombre
d’opérations élémentaires (affectation, calcul arithmétique ou logique,
comparaison…) effectuées par l’algorithme.

• Puisqu’il s’agit seulement de comparer des algorithmes, les règles de ce calcul

doivent être indépendantes :

• du langage de programmation utilisé ;

• du processeur de l’ordinateur sur lequel sera exécuté le code ;

• de l’éventuel compilateur/interpréteur employé.

13
Complexité temporelle d’un algorithme
• Comment calculer la complexité temporelle?
• Pour simplicité, on fera l’hypothèse que toutes les opérations
élémentaires sont à égalité de coût, soit 1 « unité » de temps.

• La complexité en temps d’un algorithme sera exprimé par une

fonction, notée 𝑇 (Temps ou Time), qui dépend de la taille des
données passées en paramètres : plus ces données seront
volumineuses, plus il faudra d’opérations élémentaires pour les traiter.
On notera 𝑛 le nombre de données à traiter.

14
Complexité temporelle
• Comment calculer la complexité temporelle?
• La fonction 𝑇(𝑛) qui est le coût (en temps) d'un algorithme est l'ordre de
grandeur du nombre d'opérations élémentaires que doit effectuer un algorithme
pour résoudre le problème auquel il est destiné.

15
Complexité temporelle

𝑪𝒐û𝒕(𝑨) = 𝑪𝒐û𝒕(𝒊𝒏𝒔𝒕𝒓𝟏) + 𝑪𝒐û𝒕(𝒊𝒏𝒔𝒕𝒓𝟐) + 𝑪𝒐û𝒕(𝒊𝒏𝒔𝒕𝒓𝟑)

𝐶𝑜û𝑡(𝑖𝑛𝑠𝑡𝑟1) = 𝐶𝑜û𝑡(𝑎𝑑𝑑𝑖𝑡𝑖𝑜𝑛) + 𝐶𝑜û𝑡(𝐴𝑓𝑓𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛) = 1 + 1 = 2
𝐶𝑜û𝑡(𝑖𝑛𝑠𝑡𝑟2) = 𝐶𝑜û𝑡(𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛) + 𝐶𝑜û𝑡(𝐴𝑓𝑓𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛) = 1 + 1 = 2
𝐶𝑜û𝑡(𝑖𝑛𝑠𝑡𝑟1) = 𝐶𝑜û𝑡(𝑑𝑖𝑣𝑖𝑠𝑖𝑜𝑛) + 𝐶𝑜û𝑡(𝐴𝑓𝑓𝑒𝑐𝑡𝑎𝑡𝑖𝑜𝑛) = 1 + 1 = 2
𝑪𝒐û𝒕 𝑨 = 𝟐 + 𝟐 + 𝟐 = 𝟔
Le coût de l’algorithme A est un coût constant
16
Complexité temporelle
• Comment calculer le coût des instructions composées?

17
 Complexité temporelle
• Comment calculer le coût des instructions composées?

𝑪𝒐û𝒕 𝑩
= 𝑪𝒐û𝒕 𝒕𝒆𝒔𝒕 + 𝒎𝒂𝒙 𝑪𝒐û𝒕 𝒂𝒇𝒇𝒆𝒄𝒕𝒂𝒕𝒊𝒐𝒏 + 𝒅𝒊𝒗𝒊𝒔𝒊𝒐𝒏 , 𝑪𝒐û𝒕 𝒂𝒇𝒇𝒆𝒄𝒕𝒂𝒕𝒊𝒐𝒏 + 𝒂𝒅𝒅𝒊𝒕𝒊𝒐𝒏 + 𝒂𝒇𝒇𝒆𝒄𝒕𝒂𝒕𝒊𝒐𝒏 + 𝒅𝒊𝒗𝒊𝒔𝒊𝒐𝒏
= 𝟏 + 𝟏 + 𝐦𝐚𝐱 𝟐, 𝟒 = 𝟏 + 𝟒 = 𝟓
Le coût de l’algorithme B est un coût constant
18
Complexité temporelle
• Comment calculer le coût des instructions composées?

𝐶𝑜û𝑡(𝐶) = ∑

𝑪𝒐û𝒕 𝑪 = 𝒏 × 𝑪𝒐û𝒕 𝒕𝒆𝒔𝒕 + 𝑪𝒐û𝒕 𝒂𝒇𝒇𝒆𝒄𝒕𝒂𝒕𝒊𝒐𝒏 + 𝒂𝒅𝒅𝒊𝒕𝒊𝒐𝒏 + 𝑪𝒐û𝒕(𝒂𝒇𝒇𝒆𝒄𝒕𝒂𝒕𝒊𝒐𝒏 + 𝒂𝒅𝒅𝒊𝒕𝒊𝒐𝒏)

= 𝒏 × 𝟏 + 𝟏 + 𝟏 + 𝟏 + 𝟏 = 𝟓𝒏
Le coût de l’algorithme C est un coût linéaire en fonction de n
19
Complexité temporelle
• Comment calculer la complexité d’un algorithme?

20
Complexité temporelle
• Comment calculer la complexité d’un algorithme?
• La fonction 𝑇(𝑛) qui est le coût (en temps) d'un algorithme est l'ordre de
grandeur de la des opérations élémentaires et composées que doit effectuer un
algorithme pour résoudre le problème auquel il est destiné.

• On parlera de :

• coût constant s'il ne dépend pas de la taille de 𝑛 : 𝑂(1)

• coût linéaire s'il est une fonction linéaire qui dépend de n c-à-d d'ordre 𝑛: 𝑂(𝑛)

• coût quadratique s'il est "d'ordre" 𝑛2 : 𝑂(𝑛2 )

• coût exponentielle si "l'ordre" est de la forme d'une puissance où apparaît en

exposant, le 𝑛.
21
La notation 0 (Grand O)
• Définition
• Soit 𝑇(𝑛) une fonction qui désigne le temps de calcul d'un algorithme A.
• On dit que 𝑇(𝑛) 𝑒𝑠𝑡 𝑒𝑛 𝑔𝑟𝑎𝑛𝑑 𝑂 𝑑𝑒 𝑓(𝑛) :
𝑻 𝒏 = 𝑶 𝒇 𝒏 𝒔𝒊 𝒆𝒕 𝒔𝒆𝒖𝒍𝒆𝒎𝒆𝒏𝒕 𝒔𝒊 ∶ ∃ 𝒏𝟎 , 𝒄 𝒕𝒆𝒍𝒍𝒆 𝒒𝒖𝒆 𝑻 𝒏 <= 𝒄 × 𝒇 𝒏 ∀𝒏
≥ 𝒏𝟎
• Exemple 1 :
• 𝑠𝑖 𝑇(𝑛) = 3𝑛 + 6 𝑎𝑙𝑜𝑟𝑠 𝑇(𝑛) = 𝑂(𝑛)
• Démonstration : pour 𝑛 >= 2, on a 3𝑛 + 6 <= 9𝑛 ; la quantité 3𝑛 + 6 est donc
bornée à partir d'un certain rang, par le produit de 𝑛 et d'une constante.
• Exemple 2:
• 𝑠𝑖 𝑇(𝑛) = 𝑛2 + 3𝑛 𝑎𝑙𝑜𝑟𝑠 𝑇(𝑛) = 𝑂(𝑛2 )
• Démonstration : pour 𝑛 >= 3, on a 𝑛2 + 3𝑛 <= 2 𝑛2 ; la quantité 𝑛2 + 3𝑛 est
donc bornée, à partir d'un certain rang, par le produit de 𝑛2 et d'une constante.
22
Classes de complexité usuelles

23
 Complexité temporelle
• Exemple de la complexité d’une boucle d’affichage simple

24
Complexité temporelle
• Exemple de calcul de la complexité d’un algorithme itératif

×𝒏
× 𝟐𝒏
× (𝟓𝒏 − 𝟏 − 𝒏 + 𝟏)

𝐓 𝒏 = 𝑶(𝒏𝟑 )
25
Complexité temporelle
• Exemple de calcul de la complexité de la fonction factorielle

affectation+addition:2
retour: 1

𝑻 𝒏 =𝟏+𝟏+ 𝒏−𝟏 × 𝟏+𝟐+𝟐 +𝟏

𝑻(𝒏) = 𝟑 + 𝟓 𝒏 − 𝟏
𝑻 𝒏 = 𝟓𝒏 − 𝟐
𝑻 𝒏 = 𝟎(𝒏) 26
Complexité temporelle
• Exemple de calcul de la complexité d’une fonction qui calcule
• Version 1

27
Complexité temporelle
• Exemple de calcul de la complexité d’une fonction qui calcule
• Version 2

28
Complexité temporelle
• Exemple de calcul de la complexité de 2 fonctions qui calculent

!
29
Complexité de quelques opérations
sur les listes

30
Exercices
1. Calcul de la complexité de la fonction append dans une liste

31
 Exercices
2. Calcul de la complexité de la fonction insert dans une liste

32
Exercices
3. Calcul de la complexité d’une fonction de saisie d’un tableau

33
Exercices
4. Calcul de la complexité d’une fonction de saisie d’une matrice

34
Exercices
5. Calcul de la complexité du produit matriciel

35
Exercices
6. Calcul de la complexité de la procédure de Tri par sélection

36
 Exercices
6. Calcul de la complexité de la procédure de Tri par sélection

Principe
• Le tri par sélection d’un tableau
consiste à rechercher le plus
petit élément et à le placer en
0, le second plus petit élément
et à le placer en 1, etc.

37
Exercices
6. Calcul de la complexité de la procédure de Tri par sélection

38
 Exercices
6. Calcul de la complexité de la procédure de Tri par sélection

× (𝒏 − 𝟏)
𝟏 𝒏−𝟐 𝒏−𝟐 𝒏−𝟏
× (𝒏 − 𝟏 − 𝒊) 𝑪ô𝒖𝒕 𝑻𝒓𝒊𝑺𝒆𝒍𝒆𝒄𝒕𝒊𝒐𝒏 = ෍ 𝟑 + ෍ ෍ 𝟐
𝒊=𝟎 𝒊=𝟎 𝒋=𝒊+𝟏
𝟏+𝟏 𝑪ô𝒖𝒕 𝑻𝒓𝒊𝑺𝒆𝒍𝒆𝒄𝒕𝒊𝒐𝒏 = 𝟑 𝒏 − 𝟏 + 𝒏 𝒏 − 𝟏
𝑪ô𝒖𝒕 𝑻𝒓𝒊𝑺𝒆𝒍𝒆𝒄𝒕𝒊𝒐𝒏 = 𝒏𝟐 + 𝟐𝒏 − 𝟑
𝑪ô𝒖𝒕 𝑻𝒓𝒊𝑺𝒆𝒍𝒆𝒄𝒕𝒊𝒐𝒏 = 𝑶(𝒏𝟐 )

𝟏+𝟏

39
Exercices
7. Calcul de la complexité de la procédure de recherche séquentielle

𝑪ô𝒖𝒕 𝑹𝒆𝒄𝒉𝒆𝒓𝒄𝒉𝒆_𝑺𝒆𝒒 = 𝟏 + 𝒏 × 𝟏 + 𝟏 + 𝟏 + 𝟐
𝑪ô𝒖𝒕 𝑹𝒆𝒄𝒉𝒆𝒓𝒄𝒉𝒆_𝑺𝒆𝒒 = 𝟑 + 𝟑𝒏
𝑪ô𝒖𝒕 𝑹𝒆𝒄𝒉𝒆𝒓𝒄𝒉𝒆_𝑺𝒆𝒒 = 𝑶(𝒏)
40
Exercices
8. Calcul de la complexité de la recherche dichotomique

41
Exercices
8. Calcul de la complexité de la recherche dichotomique

Principe
• On cherche dans un tableau 𝑳 une valeur 𝒗 . Un pointeur 𝒎 est initialisé
au « milieu » du tableau . On a alors 3 cas :
• Si 𝒗 > 𝑳[𝒎] , cela signifie qu’elle se trouve à un indice entre 𝒎 et
celui de la dernière valeur du tableau : soit « après » 𝒎 .
• Si 𝒗 < 𝑳[𝒎] , cela signifie que la valeur recherché se trouve « avant »
𝒎.
• On recommence la même opération avec la « moitié » du tableau qui
est sensée contenir la valeur recherchée, jusqu’à ce qu’elle soit
trouvée, ou que la liste ne comporte plus qu’un seul élément.
• Si la valeur recherchée et égale à la valeur 𝑳[𝒎] , c’est qu’on l’a
trouvée !!
42
Exercices
8. Calcul de la complexité de la recherche dichotomique
𝑺𝒐𝒊𝒕 𝑳 𝒖𝒏𝒆 𝒍𝒊𝒔𝒕𝒆 𝒕𝒓𝒊é𝒆 𝒅𝒆 𝟏𝟕 é𝒍𝒆𝒎𝒆𝒏𝒕𝒔, 𝒐𝒏 𝒗𝒆𝒖𝒕 𝒄𝒉𝒆𝒓𝒄𝒉𝒆𝒓 𝒍𝒂 𝒗𝒂𝒍𝒆𝒖𝒓 𝟑𝟏

𝒎 43
Exercices
8. Calcul de la complexité de la recherche dichotomique

𝑶(𝟏)
Quel
est
le nombre
d’itérations
de la
Boucle
𝐰𝐡𝐢𝐥𝐞?

𝑶(𝟏) 44
Exercices
8. Calcul de la complexité de la recherche dichotomique

45