24/04/2022
1. Notion de la complexité
La théorie de la complexité algorithmique vise à:
classer les problèmes selon leur difficulté,
Chapitre 7 : Coût d’un algorithme classer les algorithmes selon leur efficacité,
& comparer les algorithmes résolvant un même
problème.
Classes de complexité
164
164 165
2. Complexité d’un algorithme 3. Complexité temporelle
Dans l’étude de la complexité d’un algorithme on ne mesure pas la La complexité temporelle d'un algorithme consiste à calculer
durée en heures, minutes, secondes, ... le nombre d'opérations élémentaires (affectations,
Ces mesures ne seraient pas pertinentes car le même algorithme sera comparaisons, opérations arithmétiques,…) effectuées par un
plus rapide sur une machine plus puissante algorithme.
L’étude de complexité consiste donc à utiliser des unités de temps Ce nombre s'exprime en fonction de la taille n des données.
abstraites proportionnelles au nombre d'opérations effectuées ; On distingue:
On pourra par la suite adapter ces quantités en fonction de la La complexité au pire: temps d'exécution maximum, dans le
machine sur laquelle l'algorithme s'exécute ; cas le plus défavorable.
166 167
, 24/04/2022
3. Complexité temporelle 4. Calcul du coût d’un programme
La complexité au mieux: temps d'exécution minimum, dans Calculer le coût d’un programme revient à calculer le nombre
le cas le plus favorable. d’opérations effectuées en fonction de la taille des données
La complexité moyenne: temps d'exécution dans un cas Pour déterminer le coût d’un algorithme, on se fonde en
médian, ou moyenne des temps d'exécution. général sur le modèle de complexité suivant :
Une affectation, une comparaison ou l’évaluation d’une expression
On s’intéresse le plus souvent au calcul de la arithmétique (+,-,/,*,DIV,MOD,^) ayant en général un faible temps
d’exécution considéré comme l’unité de mesure du coût d’un
complexité au pire, car on veut borner le temps
algorithme ou d’un programme.
d'exécution
168 169
4. Calcul du coût d’un programme 4. Calcul du coût d’un programme
Le coût d’une boucle Pour est le nombre de répétitions multiplié par
Le coût des instructions p et q en séquence est la somme des coûts de
le coût du bloc d’instructions p.
l’instruction p et de l’instruction q.
Pour i de 1 à n Faire
Le coût d’un test Si est le Maximum des coûts des instructions p et q, p
plus le temps d’évaluation de l’expression b. FinPour
Si b Alors Le cas d’une boucle TantQue est plus complexe à traiter puisque le
p nombre de répétitions n’est en général pas connu a priori. On peut
Sinon
majorer le coût de l’exécution de la boucle par le nombre de
q
Finsi répétitions effectuées.
TantQue (condition) Faire
p
FinTQ
170 171
1. Notion de la complexité
La théorie de la complexité algorithmique vise à:
classer les problèmes selon leur difficulté,
Chapitre 7 : Coût d’un algorithme classer les algorithmes selon leur efficacité,
& comparer les algorithmes résolvant un même
problème.
Classes de complexité
164
164 165
2. Complexité d’un algorithme 3. Complexité temporelle
Dans l’étude de la complexité d’un algorithme on ne mesure pas la La complexité temporelle d'un algorithme consiste à calculer
durée en heures, minutes, secondes, ... le nombre d'opérations élémentaires (affectations,
Ces mesures ne seraient pas pertinentes car le même algorithme sera comparaisons, opérations arithmétiques,…) effectuées par un
plus rapide sur une machine plus puissante algorithme.
L’étude de complexité consiste donc à utiliser des unités de temps Ce nombre s'exprime en fonction de la taille n des données.
abstraites proportionnelles au nombre d'opérations effectuées ; On distingue:
On pourra par la suite adapter ces quantités en fonction de la La complexité au pire: temps d'exécution maximum, dans le
machine sur laquelle l'algorithme s'exécute ; cas le plus défavorable.
166 167
, 24/04/2022
3. Complexité temporelle 4. Calcul du coût d’un programme
La complexité au mieux: temps d'exécution minimum, dans Calculer le coût d’un programme revient à calculer le nombre
le cas le plus favorable. d’opérations effectuées en fonction de la taille des données
La complexité moyenne: temps d'exécution dans un cas Pour déterminer le coût d’un algorithme, on se fonde en
médian, ou moyenne des temps d'exécution. général sur le modèle de complexité suivant :
Une affectation, une comparaison ou l’évaluation d’une expression
On s’intéresse le plus souvent au calcul de la arithmétique (+,-,/,*,DIV,MOD,^) ayant en général un faible temps
d’exécution considéré comme l’unité de mesure du coût d’un
complexité au pire, car on veut borner le temps
algorithme ou d’un programme.
d'exécution
168 169
4. Calcul du coût d’un programme 4. Calcul du coût d’un programme
Le coût d’une boucle Pour est le nombre de répétitions multiplié par
Le coût des instructions p et q en séquence est la somme des coûts de
le coût du bloc d’instructions p.
l’instruction p et de l’instruction q.
Pour i de 1 à n Faire
Le coût d’un test Si est le Maximum des coûts des instructions p et q, p
plus le temps d’évaluation de l’expression b. FinPour
Si b Alors Le cas d’une boucle TantQue est plus complexe à traiter puisque le
p nombre de répétitions n’est en général pas connu a priori. On peut
Sinon
majorer le coût de l’exécution de la boucle par le nombre de
q
Finsi répétitions effectuées.
TantQue (condition) Faire
p
FinTQ
170 171
