IPEIT 2022/2023
Notion de complexité
Pour traiter un même problème, il existe souvent plusieurs algorithmes. Quel sont les critères
utilisés pour choisir l’algorithme le plus efficace ?
Définition :
Déterminer la complexité d’un algorithme c’est évaluer les ressources nécessaires à son
exécution (la quantité de mémoire requise) et le temps de calcul à prévoir, ces deux notions
dépendent de nombreux paramètres matériels qui sortent du domaine de l’algorithmique.
Nous ne pouvons attribuer une valeur absolue ni à la quantité mémoire requise, ni au temps
d’exécution d’un algorithme donné. En revanche, il est souvent possible d’évaluer l’ordre de
grandeur de ces deux quantités.
D’où on a deux notions de complexité :
complexité temporelle qui est donnée par l’évaluation de l’ordre de grandeur du temps
d’exécution appelé aussi coût d’un algorithme.
complexité spatiale qui est donnée par l’évaluation de l’ordre de grandeur du volume
en mémoire utilisé.
Modèle de complexité pour déterminer le coût d’un algorithme :
une affectation, une comparaison, l’évaluation d’une opération arithmétique ayant
en général un faible temps d’exécution unité de mesure de coût d’un algorithme
les coûts des instructions p et q en séquence égale à la somme des coûts de p et q.
le coût d’un test si cond alors p sinon q fsi est inférieur ou égale au maximum de
coûts de p et q plus le temps d’évaluation de cond.
Pour la boucle pour, si le coût du corps de la boucle ne dépend pas du compteur
alors le coût total est le coût du corps multiplié par le nombre d’itérations sinon le
coût total égale à la somme des coûts du corps pour chaque valeur du compteur.
Pour la boucle tant que ou répéter le nombre de répétitions est inconnu, on peut
majorer le nombre de répétitions et ainsi majorer le coût de l’exécution de la
boucle.
Notation :
La complexité est donnée par l’ordre de grandeur du terme dominant dans le temps
d’exécution d’un algorithme.
Par exemple, si on a déterminé que le temps d’exécution était proportionnel à , dès
que la taille n des données devient un peu importante, il est connu que le terme augmente
beaucoup moins vite que : on dit qu’il est négligeable devant ce dernier. Pour décrire
l’efficacité d’un algorithme, seul le terme qui crois plus vite a donc un intérêt par exemple, ici
pour on a ; la quantité est donc bornée, à partir d’un certain
rang, par le produit de et une constante. on dit alors que la quantité est de l’ordre
de et on écrira .
De manière générale, on dira qu’un algorithme a une complexité en ( ) si son coût est,
à partir d’un certain rang, inférieur au produit de par une constante.
( )
[Link] 1/2
IPEIT 2022/2023
Exemples :
Donner les coûts des traitements suivants :
for i in range(n) :
x=x+1 coût :3*n complexité : O(n)
print(x)
for i in range(n) :
for j in range(2,n) :
x=x+1 coût :3n(n-2) complexité :O(n2)
print(x)
for i in range(n) :
for j in range(i,n) :
x=x+1 coût: 3n (n-1)/2 complexité : O(n2)
print(x)
i=n
while i>=1 :
print(x) coût :3*log(n)+1 complexité : O(log(n))
i=i / /2
for a in range(n) :
for b in range(n) :
for c in range(n) :
. k boucles complexité : O(nk)
.
.
for p in range(n) :
Traitement
Ordre de grandeurs et temps d’exécution :
On s’appuyant sur une base de 109 opérations par seconde on obtient :
Linéaire : Logarithmique : Semi-linéarie : Quadratique : Polynomial :
O(n) O(log(n)) O(nlog(n)) O(n2) O(n3)
102 7 ns 100 ns 0,7 µs 10 µs 1 ms
103 10 ns 1 µs 10 µs 1ms 1s
104 13 ns 10 µs 133 100ms 17s
105 17 ns 100 µs 2 ms 10 s 11,6 j
106 20 ns 1 ms 20 ms 17 mn 32 a
[Link] 2/2