Institut Préparatoire aux Etudes d’Ingénieur de Bizerte

Lundi 05 - 4 - 2021

Complexité d’un algorithme

PC 1 - MP 1

Année Universitaire 2020 - 2021

Enseignant : Rouissi Tawfik

 [Link]

 L théorie
La thé i de
d la
l complexité
l ité algorithmique
l ith i vise
i à:à
◦ classer les problèmes selon leur difficulté,
◦ classer les algorithmes selon leur efficacité,
efficacité
◦ comparer les algorithmes résolvant un même problème.

Proposer en Python deux programmes différents

pour vérifier la primalité d’un entier n?

Proposer en Python deux programmes différents

pour calculer xn?

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015

2
 [Link]

 Pour mesurer le temps d'exécution d’un programme en

Python nous pouvons simuler un chronomètre :
◦ on le déclenche juste avant le début du programme
programme,
◦ on l'arrête juste après la fin du programme,
◦ le temps écoulé entre les deux pressions est la durée qui nous
intéresse.
 En Python, on peut simuler un chronomètre grâce au
module time ;

Exemple:

ffrom time
i i
import *
debut = time() # on déclenche le chronomètre
ot e p
# votre programme
og a e
fin = time() # on arrête le chronomètre
print(’Temps écoulé:’, fin - debut, ’ secondes’)

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015

3
 [Link]
Ecrire un programme Python pour vérifier la
primalité
i lité de
d n??
Programme naïf: vérifier si n possède un diviseur dans
l’intervalle [2,n-1]

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 4
 [Link]
Ecrire un programme Python pour vérifier la
primalité de n?
Programme rapide: vérifier si n possède un diviseur dans
ll’intervalle
intervalle [2
[2,n],
n]

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
5
 [Link]
Ecrire un programme Python pour calculer xn?

Méthode classique:
Xn=x*x*………….*x
x*x* *x
n fois

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
6
 [Link]
Exponentiation rapide

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 7
 [Link]

Dans l’étude
D l’ét d de
d complexité
l ité d’un
d’ algorithme
l ith on ne mesure pas
la durée en heures, minutes, secondes, ...:
◦ cela impliquerait dd'implémenter
implémenter les algorithmes qu qu'on
on
veut comparer ;
◦ de plus, ces mesures ne seraient pas pertinentes car le
même algorithme sera plus rapide sur une machine plus
puissante ;

L’étude de complexité consiste donc à utiliser

des unités de temps abstraites proportionnelles
au nombre d'opérations effectuées ;
On pourra par la suite adapter ces quantités en
fonction de la machine sur laquelle l'algorithme
s'exécute
s exécute ;
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
8
 [Link]
 La complexité temporelle d'un algorithme
consiste à calculer le nombre d d'opérations
opérations
élémentaires (affectations, comparaisons,
opérations
p arithmétiques,…)
q , ) effectuées ppar un
algorithme.
 Ce nombre s'exprime en fonction de la taille n
des données.
 On s'intéresse:
◦ La complexité au pire: temps d'exécution maximum,
dans le cas le plus défavorable.
◦ La complexité au mieux: temps d d'exécution
exécution minimum,
minimum
dans le cas le plus favorable.
◦ La complexité moyenne: temps d'exécution dans un cas
édi
médian, ou moyenne d des ttemps d' é ti
d'exécution.
 Le plus souvent, on calcule la complexité au pire,
car on veut borner le temps d'exécution
d exécution
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
9
 [Link]

 Calculer le coût d’un

d un programme revient à calculer le
nombre d’opérations effectuées en fonction de la taille
des données
 Pour déterminer le coût d’un algorithme, on se fonde en
général sur le modèle de complexité suivant :
◦ Une affectation,
ff une comparaison ou l’évaluation
l’é l d’
d’une
expression arithmétique (+,-,/,*,//,%,**) ayant en
général un faible temps dd’exécution
exécution considéré comme
l’unité de mesure du coût d’un algorithme.
◦ Le coût des instructions p et q en séquence est la
somme des coûts de l’instruction p et de l’instruction q.

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 10
 [Link]

◦ Le coût d’un
d un test if
if b:
p
else:
q
Le coût d’un test est égal au maximum des coûts des instructions
p et q, plus le temps d’évaluation de l’expression b.
◦ Le coût d’une boucle for
for i in range(n):
p
L coût
Le û d’une
d’ b
boucle
l for
f est égal
é l au nombreb de d répétitions
é éii
multiplié par le coût du bloc d’instructions p.
Quand le coût de p dépend
Q p de la valeur de i,, le coût total de la
boucle est la somme des coûts de p pour chaque valeur de i.

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
11
 [Link]

◦ Le cas d’une
d une boucle while
while condition:
p

Le cas d’une boucle while est p

plus complexe
p à traiter
puisque le nombre de répétitions n’est en général pas
connu a priori.

On peut majorer le coût de l’exécution de la boucle par

l nombre
le b dde répétitions
é étiti effectuées.
ff t é

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
12
 [Link]

 Exemple:
◦ Calculer la factorielle d’un entier n

1 affectation

(n-1) itérations
1 affectation + 1 multiplication

1 renvoi

Le coût de l’algorithme
l algorithme = Nombre total d’opérations
d opérations
1 Affectation + (n-1) *( 1 affectation + 1 multiplication)+1 renvoi

f( ) 1+ ((n-1)*2+1=2*n
f(n)=1+ 1)*2+1 2*

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 13
 [Link]

 Exemple:
◦ Vérifier la primalité d’un entier n

(n-2) itérations
1 reste + 1 comparaison
1 renvoi

1 renvoi
f1(n)=(n-2)*2+1
=2n-3

(n-1)
  itérations
1 reste + 1 comparaison
1 renvoi

1 renvoi

n=2**31-1 f2(n)=(n-1)*2+1
f1( ) 4294967293
f1(n)= =2*n-1
f2(n)= 92679
14
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016
 [Link]

 Exemple: Calculer xn
1 affectation
n itérations
1 affectation + 1 multiplication

1 renvoi

f1(n)=1+n*2+1
=2n+2
2 2
1 affectation
(log2(n)) itérations
1 comparaison
i
1 reste + 1 comparaison
1 affectation + 1 multiplication
1 affectation + 1 division
1 affectation + 1 multiplication
1 renvoi
f2(n)=1+ (log2(n)+1) *(1+2+2+2)
+ (log2(n)+1) *2+1
=9*log2(n)+11
La représentation binaire de n nécessite (log2(n)+1) bits
Le coût
û maximall sur (log
(l 2(n)+1)
( ) ) b
bits = 9*log
9 l 2(n)+11
( )
X=3 et n=2**20-1
f1(n)= 2097152 et f2(n)=182 Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016
15
 [Link]

Calculer le coût des p

programmes
g suivants

1 affectation
n itérations
1 affectation + 1 addition
1 renvoi

f1(n)=1+n*2+1
=2n+2
2 2
1 affectation
n itérations
n itérations
1 affectation + 1 addition
+ 1 multiplication
1 renvoi

f2(n)=1+n*n*3+1
=3n2+2

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 16
 [Link]

Calculer le coût des p

programmes
g suivants

1 affectation
n itérations
i itérations
1 affectation + 1 addition
+ 1 multiplication
1 renvoi

f1(n)=1+(n*(n+1)/2)*3+1
=(3/2)n2+(3/2)n+2

1 affectation
log2(n)  itérations
1 affectation + 1 multiplication
1 condition
1 condition
1 renvoi

f2(n)=1+log2(n) l ( ) *3+1+1
=3*log2(n) +3
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 17
 [Link]

 Généralement, la complexité d'un algorithme

est une mesure de sa performance
asymptotique dans le pire cas ;
 Que signifie ‘asymptotique’ ?
◦ on s'intéresse à des données très grandes ;
 Que signifie ‘dans le pire cas’ ?
◦ on s'intéresse à la performance de l'algorithme dans
les situations où le problème prend le plus de temps.
 Pourquoi ?
◦ pour être
ê sûr
û que l'algorithme ne prendra jamais plus
de temps que ce qu'on a estimé. Ce qui correspond à
donner une majoration du nombre d’opérations
d opérations
effectuées par l’algorithme.

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015

18
 [Link]

 On dit que la complexité de l'algorithme est

O(g(n)) ou g est d'habitude une
combinaison de p polynômes,
y logarithmes
g ou
exponentielles.
 Ce qui signifie que le nombre d d'opérations
opérations
effectuées, noté par f(n), est borné par
C*g(n)
C g(n), ou C est une constante,
constante lorsque n
tend vers l'infini.

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
19
 [Link]

Si f et g sont deux fonctions positives réelles:

f(n) = O(g(n)) si et seulement si le rapport f/g est
borné a l'infini (f est dominée par g):
∃C>0 ∃n0>0,
◦ ∃C>0, >0 n>n0, f(n) ≤ C
C*g(n)
g(n)
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
20
 [Link]

 La notation O, dite notation de Landau,

Landau vérifie
les propriétés suivantes :

 si f=O(g) et g=O(h) alors f=O(h)

 sii ff=O(g)
O( ) ett c>0,
>0 alors
l c*f=O(g)
*f O( )
 si f1=O(g1) et f2=O(g2) alors f1+f2 = O(g1+g2)
 si f
f1=O(g1)
( ) et ff2=O(g2)
( ) alors
l ff1*f2
f = O(g1*g2)
( )

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 21
 [Link]

Si f et g sont deux fonctions positives réelles:

f(n) = (g(n)) ⇒ g est une borne inférieure
asymptotique pour f:
∃C>0 ∃n0>0,
◦ ∃C>0, >0 n>n0, C
C*g(n)
g(n) ≤f(n)
Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
22
 [Link]

Si f et g sont deux fonctions positives réelles:

 f(n) = Θ(g(n)) ⇒f et g ont le même ordre de grandeur :
◦ ∃c1,c2>0, ∃n0>0, n>n0, c1*g(n) ≤ f(n) ≤c2*g(n)

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
23
 [Link]

 O(1) : complexité constante, pas d

d'augmentation
augmentation du
temps d'exécution quand le paramètre croit.
◦ Exemple: affectation, comparaison, …
 O(log(n)) : complexité logarithmique
logarithmique, augmentation
très faible du temps d'exécution quand le paramètre
croit.
◦ Exemple: conversion du décimal au binaire
 O(n) : complexité linéaire, augmentation linéaire du
temps d'exécution quand le paramètre croit (si le
paramètre double
double, le temps double)
double).
◦ Exemple: somme des n premiers entiers naturels
 O(n*log(n)) : complexité quasi-linéaire, augmentation
O(n)
un peu supérieure a O(n).
 Exemple: calculer la somme des chiffres des n premiers entiers
naturels

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 24
 [Link]

 O(n2) : complexité quadratique, quand le

paramètre double, le temps d'exécution est
multiplie par 4.
◦ Exemple : algorithmes avec deux boucles imbriquées.
imbriquées
 O(ni) : complexité polynomiale, quand le
paramètre double, le temps d'exécution est
multiplie
lti li par 2i.
◦ Exemple : algorithme utilisant i boucles imbriquées.
 O(a
( n) : complexité
p exponentielle,
p ,q
quand le
paramètre double, le temps d'exécution est élevé
à la puissance 2.
 O(n!) : complexité factorielle
factorielle, asymptotiquement
équivalente à nn

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 25
[Link]

Dr. Atef MASMOUDI & Dr. Ameur CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015
26
 [Link]

On suppose ququ’on
on dispose d’un
d un ordinateur capable de
réaliser 109 opérations/seconde

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 27
 [Link]

 p
Les instructions de base (affectation, comparaison,
opération arithmétique,) prennent un temps constant,
noté O(1)
 On additionne les complexités d'opérations en séquence :

Instruction p O(f1(n))
I
Instruction
i q O(f2( ))
O(f2(n))
O(f1(n)) + O(f2(n)) = O(f1(n) + f2(n)) =O(max(f1(n), f2(n)))
 Les
L b branchements
h t conditionnels
diti l :

= O(max(f1(n) , f2(n), g(n)))

Dr. Atef MASMOUDI & Dr. Ameur
CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 28
 [Link]

 La complexité d’une boucle for est égal au nombre d’itérations

multiplié par la complexité de l’instruction p si ce dernier ne
dépend pas de la valeur de i.

O(n*f(n))

 La complexité d’une boucle while:

= O(m*max(g(n) , f(n)))

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 29
 [Link]

 p
Pour calculer la complexité d'un p g
programme :

1. on calcule la complexité de chaque partie du

programme;
2. on combine ces complexités conformément aux règles
qu'on'
vient de voir ;
3 on simplifie
3. i lifi lle résultat
é lt t grâce
â aux règles
è l d de
simplifications suivantes:
◦ II' élimination des constantes
constantes,
◦ on annule les constantes additives ;
◦ la conservation du (des) terme(s) dominant(s)
Dr. Atef MASMOUDI & Dr. Ameur
CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 30
 [Link]

O(1)

n-1 itérations O(n)

O(1)

O(1)
 La complexité de la fonction:

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 31
[Link]

O(n)

O(n)

O(n)

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 32
[Link]

O(log(n))

O(log(n))

O(log(n))

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 33
[Link]

O(n2)

O(n2)

O(n*log(n))

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 34
 [Link]

 Montrez q p
que la complexité g
de l’algorithme ci-dessous
est quadratique en n, c’est-à-dire en O(n2)

1 affectation

n itérations
1 affectation
k itérations
1 affectation + 1 multiplication

1 affectation + 1 addition
+1 division
1 renvoi

f(n)=1+n+2*(n*(n-1)/2)+3*n+1
n2+3
=n +3*n+2
n+2

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 35
 [Link]

 g
Donnez une version linéaire de cet algorithme, c’est-à-
dire en O(n)

1 affectation
1 affectation
n itérations
1 affectation +1 Multiplication
+ 1 addition

1 affectation + 1 addition
+1 division
1 renvoi

f(n)=2+6*n+1
6 n+3
=6*n+3

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 36
 [Link]

 Complétez le tableau suivant.

Il s’agit de calculer le nombre d’opérations nécessaire

pour exécuter le programme en fonction de sa
complexité et de la taille du problème traité
Complexité
p n=10 n=100 n=1000
n
n2
n3
2n
n
log(n)
Dr. Atef MASMOUDI & Dr. Ameur
CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 37
 [Link]

 Complétez le tableau suivant.

Il s’agit de calculer le temps nécessaire
é pour exécuter
é
un problème en supposant qu’on dispose d’un
ordinateur capable de réaliser 109 opérations/seconde

Complexité n=10 n=100 n=1000

n
n2
n3
2n
n
log(n)
Dr. Atef MASMOUDI & Dr. Ameur
CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 38
 [Link]

 Rangez les fonctions suivantes par ordre de

grandeur croissant :
◦ n,
n n*log(n),n,
n*log(n) n log(n),
log(n) n log2(n),n
(n) n2, (3/2)n,
n10, log2(n)

 Calculer la complexité des programmes:

 Premier et premier_rapide
 Puissance et puissance_rapide

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 39
 [Link]

 Dire si les affirmations suivantes sont vrais

ou fausses:
◦ 2n+3=O(n)
◦ 2n+log(n)=O(n2)
◦ 2n7+5n4+3n2+1=O(n ( 7)
◦ 5n3+3nlog(n)+6n=O(n3)
◦ 3log(n)+2=O(log(n))
◦ 2n+100log(n)=O(log(n))
◦ 2n+2=O(2n)

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 40
 [Link]

 Quelle est la complexité de la fonction

suivante:

Dr. Atef MASMOUDI & Dr. Ameur

CH'HAYDER, IPEIS, AU:2015-2016 16/12/2015 41
Bon travail