Cours Complexité algorithmique (MBDS)

cours 1:Introduction à la complexité des algorithmes

Dr. Dhouha Maatar Razgallah

2017/2018

Outline
 Introduction
 Théorie de la complexité
 Complexité algorithmique
 Application de calcul de complexité: produit de matrices

1
Introduction Qu’est ce que l’algorithmique?

 L’algorithmique est l’étude des algorithmes.

 Un algorithme est une suite d’instructions qui décrit comment
résoudre un problème particulier en un temps fini.

Avez-vous déjà ouvert un livre de recettes de cuisine ?

ou déjà indiqué un chemin à un touriste?

Si oui, sans le savoir, vous avez déjà exécuté des algorithmes.

Si l’algorithme est juste, le résultat est le résultat voulu, et le touriste se retrouve là où il

voulait aller. Si l’algorithme est faux, le résultat est aléatoire, et le touriste est perdu.

Pour fonctionner, un algorithme doit contenir uniquement des instructions

compréhensibles par celui qui devra l’exécuter.
3

Introduction Algorithme et programme

 Un programme (code) : la réalisation (l’implémentation) d’un algorithme au moyen

d’un langage donné (sur une architecture donnée). Il s’agit de la mise en œuvre du principe.

Informations Résultats mis

du problème en forme
machine

Données Obtention de
structurées résultats

Traitement

2
Introduction du raisonnement à l’algorithme au code

Exemple de tâche: Décider si un tableau L est trié en ordre croissant.

 Raisonnement: Un tableau L est trié si tous ses éléments sont dans l’ordre
croissant.
 Algorithme: Une fonction vérifiant cette propriété, supposera donc le tableau L,
de taille n, trié au départ et cherchera une contradiction.
Fonction trie (L: tab, n: entier) : booleen
Variables i, n: entier; Ok: booleen
Début
Ok  vrai
pour i de 1 à n faire
si (L[i ] > L[i +1]) alors
Ok  Faux
Finsi
Finpour
Retourner OK
Fin trie
boolean trie (tab L, int n)
 Code: {
Ok =true;
For (i =0; i< n ; i++)
{ if (L[i ] > L[i +1])
Ok= Faux; } 5
return Ok;}

Introduction double problématique de l’algorithmique

 La question la plus fréquente que se pose à chaque programmeur est la

suivante:
Comment choisir parmi les différentes approches pour résoudre un problème?
Exemples: Trier un tableau: algorithme de tri par insertion ou de tri rapide?…, etc

On attend d’un algorithme qu’il résolve correctement et de manière efficace le

problème à résoudre, quelles que soient les données à traiter.

1. La correction: résout il bien le problème donné?

Trouver une méthode de résolution (exacte ou approchée) du problème.

2. L’efficacité: en combien de temps et avec quelles ressources?

Il est souhaitable que nos solutions ne soient pas lentes, ne prennent pas de
l’espace mémoire considérable.

Savoir résoudre un problème est une chose, le résoudre efficacement en est une autre!
6

3
Introduction Efficacité

L’efficacité d’un algorithme peut être évaluée par:

 Rapidité (en terme de temps d’exécution)

 Consommation de ressources (espace de stockage, mémoire utilisée)

 La théorie de la complexité étudie l’efficacité des algorithmes.

On s’intéresse dans ce cours, essentiellement, à l’efficacité en terme de temps

d’exécution.

Théorie de la complexité Définition et Objectifs

 La théorie de la complexité est une branche de l’informatique théorique, elle

cherche à calculer, formellement, la complexité algorithmique nécessaire pour
résoudre un problème P au moyen de l’exécution d’un algorithme A.

La théorie de la complexité vise à répondre aux besoins d’efficacité des

algorithmes (programmes):

Elle permet:

• Classer les problèmes selon leur difficulté.

• Classer les algorithmes selon leur efficacité.

• Comparer les algorithmes résolvant un problème donné afin de faire un choix

sans devoir les implémenter. 8

4
Théorie de la complexité Evaluation de la rapidité d’un algorithme

 On ne mesure pas la durée en heure, minute, seconde… cela impliquerait

d’implémenter les algorithmes qu’ on veut comparer.

Ces mesures ne seraient pas pertinentes car le même algorithme sera plus
rapide sur une machine plus puissante.

Au lieu de ça, on utilise des unités de temps abstraite proportionnelles au

nombre d’opérations effectuées.

Au besoin, on pourra alors adapter ces quantités en fonction de la machine sur
laquelle l’algorithme s’exécute.

Théorie de la complexité Calcul du temps d’exécution

Règles:
• Chaque instruction basique consomme une unité de temps (affectation d’une
variable, lecture, écriture, comparaison,…).

• Chaque itération d’une boucle rajoute le nombre d’unités de temps

consommés dans le corps de cette boucle.

• Chaque appel de fonction rajoute le nombre d’unités de temps consommées

dans cette fonction.

• Pour avoir le nombre d’opération effectuées par l’algorithme, on additionne

le tout.

10

5
Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

11

Théorie de la complexité Calcul du temps d’exécution

Exemple: Temps d’exécution de la fonction factorielle

L’algorithme suivant calcule : n! = n*(n-1)*(n-2)*…*1 avec 0! =1

Temps de calcul = 1+1+(2+2+1)*(n-1)+1= 5n-2 opérations

12

6
Théorie de la complexité Calcul du temps d’exécution

Problèmes
Unités de temps abstraites:
 Dépends des données.
 Dépend de la nature des données: on ne sait pas toujours combien de fois
exactement on va exécuter une boucle.
 De même lors d’un branchement conditionnel, le nombre de comparaisons
effectués n’est pas toujours le même.

Temps exacte:
 Dépend de la puissance de la machine.
 Dépend de la nature des données (variables): si on change les données, le temps
change.

Solution
Calcul de la complexité algorithmique
13

Complexité algorithmique Définition

La complexité d’un algorithme est la mesure du nombre d’opérations

fondamentales qu’il effectue sur un jeu de données. Elle est exprimée comme
une fonction de la taille du jeu de données.
Il existe trois types de complexité:
 Complexité au meilleur
C’est le plus petit nombre d’opérations qu’aura à exécuter l’algorithme sur
un jeu de données de taille n.

 Complexité au pire
C’est le plus grand nombre d’opérations qu’aura à exécuter l’algorithme
sur un jeu de données de taille n.

Complexité en moyenne
C’est la moyenne des complexités de l’algorithme sur des jeux de données
de taille n.
14

7
Complexité algorithmique Définition générale

De façon générale: La complexité d’un algorithme est une mesure de sa

performance asymptotique dans le pire des cas.

 asymptotique ?
 on s’intéresse à des données très grandes parce que les petites valeurs ne
sont pas assez informatives.

 Pire des cas ?

on s’intéresse à la performance de l’algorithme dans les situations où le
problème prend le plus de temps à résoudre parce qu’on veut être sûr que
l’algorithme ne prendra jamais plus de temps que ce qu’on a estimé.

Un algorithme est dit « optimal » si sa complexité est la complexité

minimale parmi les algorithmes de sa classe.

15

Complexité algorithmique 0-notation (Notation de Landau)

Quand on calcule la complexité d’un algorithme, on ne calcule

généralement pas sa complexité exacte, mais son ordre de grandeur.

C’est une approximation du temps de calcul de l’algorithme.

Pour ce faire, on a recours à la notation asymptotique O(.) ou

Notation de Landau.
16

8
Complexité algorithmique 0-notation (Notation de Landau)

Cette notation exprime la limite supérieure d’une fonction dans un

facteur constant.
 Soit n la taille des données à traiter, on dit qu’une fonction f(n) et en O(g(n)) si :

 f(n) et en O(g(n))s’il existe un seuil à partir duquel la fonction f(.) est toujours
dominée par g(.), à une constante multiplicative fixée près.

Utilité: Le temps d’exécution est borné

Signification: Pour toutes les grandes entrées (i.e., N >= n0), on est assuré que
l’algorithme ne prend pas plus de c*g(n) étapes.
Borne supérieure. 17

Complexité algorithmique 0-notation (Notation de Landau)

18

9
Complexité algorithmique 0-notation (Notation de Landau)

19

Complexité algorithmique Exemples de calcul de 0(.)

Exemple 1: Prouver que f1(n) = 5n+37 est en O(n)

But: trouver une constante et un seuil à partir duquel

On remarque que 5n +37 <= 6n si n >= 37

On déduit donc que c=6 fonctionne à partir de n0 =37

Remarque: on ne demande pas d’optimiser (le plus petit c ou n0 qui fonctionne)

juste il faut donner des valeurs qui fonctionnent.

20

10
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 2: Prouver que est en

But: trouver une constante et un seuil à partir duquel

Chercher d’abord c, c=6 ne peut pas marcher, donc c=7

On doit donc trouver un seuil n0 à partir du quel :

c=7 et n0 =1

21

Complexité algorithmique Exemples de calcul de 0(.)

Exemple 3: Calculer la complexité de

On remarque que

pour tout n>= 1

Donc est en

22

11
Complexité algorithmique Exemples de calcul de 0(.)

Exemple 4: Calculer la complexité de l’initialisation d’un tableau:

On remarque qu’il y a n itérations; chaque itération nécessite un temps

d’exécution <= c où c est une constante (accès au tableau + une affectation)

 le temps est donc T(n)<= c n

Donc T(n) est en O(n)

23

Complexité algorithmique Règles de calcul

On calcule le temps d’exécution, mais on effectue les simplifications

suivantes:
On oublie les constantes multiplicatives (elles valent 1)
On annule les constantes additives
On ne retient que les termes dominants

Exemple (simplifications) soit :

• On remplace les constantes multiplicatives par 1:
• On annule les constantes additives :
• On garde le terme de plus haut degré:

• On a donc la complexité de

24

12
Complexité algorithmique Règles de calcul

De façon générale, les règles de la notation en O sont les suivantes:

Les termes constants :

O(c) = O(1)
Les constantes multiplicatives sont omises:
O(cT) = c O(T)=O(T)
 L’addition est réalisée en prenant le maximum:
O(T1)+O(T2)= O(T1+T2)=max(O(T1); O(T2))
La multiplication reste inchangée:
O(T1) O(T2)= O(T1*T2)

25

Complexité algorithmique Règles de calcul

Exemple:
Supposons que le temps d’exécution d’un algorithme est décrit par la fonction:
calculer O(T(n))?

Remarque:
Pour n=10, nous avons:

Le poids de devient encore plus grand pour n=100, soit 96,7%, on peut donc négliger les
quantités10n et 10. 26
Ceci explique les règles de notation O.

13
Complexité algorithmique Calcul de complexité

 Cas d’une instruction simple : Les instructions de base (lecture, écriture,

affectation …) prennent un temps constant, noté O(1).
Cas d’une suite d’instructions: le temps d’exécution d’une séquence est
déterminé par la règle de la somme.

Cas d’une branche conditionnelle: le temps d’exécution est déterminé aussi par
la règle de la somme.

27

Complexité algorithmique Calcul de complexité

 Cas d’une boucle: On multiplie la complexité du corps de la boucle par le

nombre d’itérations.
Exemple pour la boucle while (tant que), la complexité se calcule comme suit:

Pour calculer la complexité d’un algorithme:

•On calcule la complexité de chaque partie de l’algorithme.

•On combine ces complexités conformément aux règles déjà vues.
•On effectue sur le résultat les simplifications possibles déjà vues.

28

14
Complexité algorithmique Calcul de complexité

Exemple: calcul de la complexité de la fonction factorielle

Complexité de la fonction = O(1) +O(1)+O[(n -1)*(1+1+1)]+O(1)

= O(1)+O(1)+O(n)+O(1)
= O(n)
29

Complexité algorithmique Classes de complexité

On peut ranger les fonctions équivalentes dans la même classe.

Deux algorithmes de la même classe sont considérés de même complexité.

Les classes de complexité les plus fréquentes (par ordre croissant selon O(.) )

30

15
Complexité algorithmique Classes de complexité

31

Complexité algorithmique Classes de complexité

32

16
Application de calcul de complexité multiplication de deux matrices

Ecrire un algorithme qui permet de calculer le produit C de deux matrices carré

A et B de dimension (nxn) ensuite de déterminer sa complexité?

Principe:

L’équation C=A *B s’écrit:

En développant cette équation, nous obtenons :

33

Application de calcul de complexité multiplication de deux matrices

Ecrire un algorithme qui permet de calculer le produit C de deux matrices carré

A et B de dimension (nxn) ensuite de déterminer sa complexité?
Algorithme:

Procédure MULTI-MAT(var C:mat; A, B: mat, n:entier)

Var i, j, k: entier
Début
Pour i de 1 à n faire
Pour j de 1 à n faire
C[i,j]  0
Pour k de 1 à n faire
C[i,j]  C[i,j] +A[i,k] * B[k,j]
Finpour finpour finpour
Fin 34

17
Application de calcul de complexité multiplication de deux matrices

Ecrire un algorithme qui permet de calculer le produit C de deux matrices carré

A et B de dimension (nxn) ensuite de déterminer sa complexité?
Complexité:

Procédure MULTI-MAT(var C:mat; A, B: mat, n:entier)

Var i, j, k: entier
Début
Pour i de 1 à n faire
Pour j de 1 à n faire Nbre d’iter: n
=>n*O(n*n)= O(n*n*n)
C[i,j]  0
Nbre d’iter: n Pour k de 1 à n faire
=>n*O(n)= O(n*n)
C[i,j]  C[i,j] +A[i,k] * B[k,j] Nbre d’iter: n
Finpour finpour finpour => O(n)
Fin

35

18