CSI2510Analyse PDF
CSI2510Analyse PDF
CSI2510Analyse PDF
1
Efficacité ?
Temps d'exécution ….
Qualité du résultat ….
Simplicité ….
2
Temps d’exécution d’un algorithme
diverses) 20
0
1000 2000 3000 4000
Taille d’entrée
3
Exemple
Si x est impair
return x
15 Si x est pair 15
calcul la somme S
des premiers x entiers
4 return S 10
4
Mesurer le temps d’execution
50
40
30
20
10
n
0 50 100
CSI2510 - Paola Flocchini 9
•Étude expérimentale:
– Implémenter l’algorithme
– Exécuter le programme avec des ensembles
de données de taille et de contenu variés.
– Mesurer précisément le temps d’exécution
pour chaque cas t (ms)
60
50
40
30
20
10
n
0 50 100
CSI2510 - Paola Flocchini 10
5
Etudes expérimentales
Analyse Théorique
6
Analyse des algorithmes
Opérations primitives:
opérations de bas niveau qui sont indépendantes du
langage de programmation, par exemple:
•Appel et retour d’une méthode
•Effectuer une opération arithmétique
•Comparer deux nombres, etc.
•Affectation d’une variable…
7
Pseudo-code
currentMax ← A[0]
for i ← 1 to n -1 do
{
if currentMax < A[i] then
currentMax ← A[i]
}
return currentMax
CSI2510 - Paola Flocchini 16
8
Analyse d’algorithmes - Exemple1
A
5 20 4 7 6 2 3 8 1 9
currentMax
currentMax ← A[0]
for i ← 1 to n -1 do
{
if currentMax < A[i] then
currentMax ← A[i]
}
return currentMax
CSI2510 - Paola Flocchini 17
A
5 20 4 7 6 2 3 8 1 9
currentMax 5
currentMax ← A[0]
for i ← 1 to n -1 do
{
if currentMax < A[i] then
currentMax ← A[i]
}
return currentMax
9
Analyse d’algorithmes - Exemple1
A
5 20 4 7 6 2 3 8 1 9
currentMax 5
currentMax ← A[0]
for i ← 1 to n -1 do
{
if currentMax < A[i] then
currentMax ← A[i]
}
return currentMax
currentMax 20
currentMax ← A[0]
for i ← 1 to n -1 do
{
if currentMax < A[i] then
currentMax ← A[i]
}
return currentMax
10
Analyse d’algorithmes - Exemple1
Meilleur cas
A
20 2 3 4 5 6 7 8 9 1
Pire cas
A
1 2 3 4 5 6 7 8 9 20
11
Analyse d’algorithmes - Exemple1
Exemple2:
Chercher l’indice d’une valeur
dans un tableau A de taille sizeA
Opérations: affectations et verifications
i←0 1 affectation
12
Notation asymptotique
f(n)
n0
CSI2510 - Paola Flocchini 26n
13
Quest-ce que ça
veut dire c g(n) ?
Example:
g(n) = n
2 g(n) = 2 n
14
3 g(n) = 3 n
f(n)
n0
CSI2510 - Paola Flocchini 30n
15
g(n) = n2
Exemple graphique
f(n) = 2n+1
f(n) is O(n2)
n
f(n) ≤ c g(n) for n ≥ n0
CSI2510 - Paola Flocchini 31
Mais aussi …
f(n) = 2n+1
g(n) = n
n
f(n) ≤ c g(n) for n ≥ n0
CSI2510 - Paola Flocchini 32
16
Mais aussi …
f(n) = 2n+1
2 g(n) = 2 n
n
f(n) ≤ c g(n) for n ≥ n0
CSI2510 - Paola Flocchini 33
Mais aussi …
f(n) = 2n+1
3 g(n) = 3 n
f(n) is O(n)
n
f(n) ≤ c g(n) for n ≥ n0
CSI2510 - Paola Flocchini 34
17
Mais …
n0 n
CSI2510 - Paola Flocchini 35
18
Limite supérieure - O (Grand O ou Big – Oh)
O(1) < O(log n) < O(n) < O(n log n) < O(n2) <
O(n3) < O(2n) … mémorisez !!
n2 1
n+
log(n)
n0 n
n0 n
CSI2510 - Paola Flocchini 37
n= 2 16 256 1024
log log n 0 2 3 3.32
log n 1 4 8 10
n 2 16 256 1024
n log n 2 64 448 10 200
n2 4 256 65 500 1.05 * 106
19
Théorème: Limite supérieure - O (Grand O ou Big – Oh)
Si g(n) est O(f(n)) , alors pour n'importe quelle
constante c >0 g(n) est aussi O(c f(n))
Théorème:
si f1(n)=O(g1(n)) et f2(n)=O(g2(n)) alors
f1(n)+f2(n)=O(max(g1(n),g2(n)))
Ex 1:
2n3 + 3n2 = O (max(2n3, 3n2))
= O(2n3) = O(n3)
Ex 2:
n2 + 3 log n – 7 = O(max(n2, 3 log n – 7))
= O(n2)
CSI2510 - Paola Flocchini 39
20
Limite supérieure - O (Grand O ou Big – Oh)
Notation asymptotique
(terminologie)
Types de complexité :
1E+30
1E+28 Cubic
constant: O(1) 1E+26
Quadratic
1E+24
logarithmique: O(log n) 1E+22
Linear
1E+20
linéaire: O(n) 1E+18
1E+16
quadratique:
T (n )
O(n2) 1E+14
cubique: O(n3) 1E+12
1E+10
polynomial: O(nk), k ≥ 1 1E+8
1E+6
exponentiel: O(an), n > 1 1E+4
1E+2
1E+0
1E+0 1E+2 1E+4 1E+6 1E+8 1E+10
n
21
Exemple d’analyse asymptotique
5 13 4 8 6 2 3 8 1 2
5 9 7.3 7.5 … … … … … …
CSI2510 - Paola Flocchini 43
Algorithm prefixAverages1(X, n)
22
i
5 13 4 7 6 2 3 8 1 2
j=0
5 13 4 7 6 2 3 8 1 2
j = 0,1
5 8
23
i
5 13 4 7 6 2 3 8 1 2
j = 0,1,2
5 8 7.3
5 13 4 7 6 2 3 8 1 2
j = 0,1,2,3
5 8 7.3 7.5
24
Exemple d’analyse asymptotique
Algorithm prefixAverages1(X, n)
1 + 2 + …+ (n − 1) = ?
CSI2510 - Paola Flocchini 49
• Le temps d’execution de
prefixAverages1 est
O(1 + 2 + …+ n)
7
6
• Le sommation de les
premières n éléments est 5
n (n + 1) / 2 4
– Il y a représentations 3
visuelle
2
• Alors, l’algorithme 1
prefixAverages1 est O(n2) 0
1 2 3 4 5 6
25
Donc l’algorithme prefixAverages1 a
un temps d’execution de:
O(n(n + 1) / 2)
=
O(n2)
NE PAS OUBLIER
1 + 2 + …+ n = n(n+1)
2
CSI2510 - Paola Flocchini 51
Un autre exemple:
un meilleur algorithme pour calculer les moyennes
préfixes.
Algorithm prefixAverages2(X, n)
26
i
5 13 4 7 6 2 3 8 1 2
s=0
5 13 4 7 6 2 3 8 1 2
s=5
5 8
27
i
5 13 4 7 6 2 3 8 1 2
s=18
5 8 7.3
5 13 4 7 6 2 3 8 1 2
s=22
5 8 7.3 7.5
28
Algorithm prefixAverages2(X, n)
(Limite inferieure)
f(n)
c • g(n)
n0 Flocchini
CSI2510 - Paola 58
n
29
big-Thêta (Grand Thêta)
<===>
si g(n) ∈ O(f(n))
et
f(n) ∈ O(g(n))
Exemple
Nous avons déjà vu:
f(n) = 60n2 + 5n + 1 est O(n2)
Donc: avec c = 60 et n0 = 1
f(n) ≥ c • n2 pour tout n ≥ 1
f(n) est Ω (n2)
Alors:
f(n) est O(n2)
et
f(n) est Ω(n2)
30
Intuition pour les notations
asymptotiques
Big-Oh
– f(n) est O(g(n)) si f(n) est plus petite ou égal
à g(n) quand n est grand
big-Omega
– f(n) est Ω(g(n)) si f(n) est plus grand ou égal
à g(n) quand n est grand
big-Theta
– f(n) est Θ(g(n)) si f(n) est a peu près égal à
g(n) quand n est grand
Mathématiques à réviser
Logarithmes et exposants
31
Mathématiques à réviser
t
∑ f(i) = f(s) + f(s+1) + f(s+2) + .. + f(t)
t=s
Progression géométrique
n
S = Σ r i = 1 + r + r 2 + … + rn
i=0
rS = r + r2 + … + rn + rn+1
rS - S = (r-1)S = rn+1 - 1
S = (rn+1-1)/(r-1)
If r=2,
S = (2n+1-1)
32
Progression aritmetique
n
S = Σ di = 0 + d + 2d + … + nd
i=0
= nd+(n-1)d+(n-2)d + … + 0
2S = nd + nd + nd + …+ nd
= (n+1) nd
S = d/2 n(n+1)
forCSI2510
d=1- Paola Flocchini
S = 1/2 n(n+1) 65
33