ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Conception et analyse d’algorithmes
Nour Houda Dougui
(cid:201)cole Nationale des Sciences de l’Informatique
deuxiŁme annØe (2013-2014)
Nour Houda Dougui
Conception et analyse d’algorithmes
1
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Plan
1 ComplexitØ des algorithmes
2 ComplexitØ des problŁmes
3 Paradigmes de programmation
4 Les arbres ØquilibrØs
Nour Houda Dougui
Conception et analyse d’algorithmes
2
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Plan
1 ComplexitØ des algorithmes
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
2 ComplexitØ des problŁmes
3 Paradigmes de programmation
4 Les arbres ØquilibrØs
Nour Houda Dougui
Conception et analyse d’algorithmes
3
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Qu’est ce qu’un algorithme ?
Un algorithme est un ensemble d’actions visant un objectif :
rØsoudre un problŁme donnØ. Il :
agit sur des donnØes initiales (entrØes),
produit des rØsultats (sorties) ou des e(cid:27)ets,
doit se terminer sur toutes les donnØes possibles du problŁme
et doit fournir une solution correcte dans chaque cas.
Programmation d’un algorithme :
expression dans un langage de programmation,
utilisation d’une machine donnØe (processeur, mØmoire),
un seul algorithme, plusieurs programmes (variantes)
styles de programmation (itØrative, rØcursives...)
Nour Houda Dougui
Conception et analyse d’algorithmes
4
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Motivation de calcul de complexitØ
Pour un problŁme donnØ, il existe souvent plusieurs algorithmes. Y
a-t-il un intŒret (cid:224) choisir ? et si oui comment choisir ?
Nour Houda Dougui
Conception et analyse d’algorithmes
5
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Motivation de calcul de complexitØ
Pour un problŁme donnØ, il existe souvent plusieurs algorithmes. Y
a-t-il un intŒret (cid:224) choisir ? et si oui comment choisir ?
Nour Houda Dougui
Conception et analyse d’algorithmes
5
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Motivation de calcul de complexitØ
Pour un problŁme donnØ, il existe souvent plusieurs algorithmes. Y
a-t-il un intŒret (cid:224) choisir ? et si oui comment choisir ?
Le nombre d’ordres possibles d’une liste de n ØlØments est n!. Si on
applique une opØration simple (cid:224) toutes les listes ordonnØes possibles
(cid:224) n ØlØments → avec le meilleur calculateur existant, au cours d’une
seconde, on est limitØ aux listes de 17 ØlØments (17! = 3, 551014).
Nour Houda Dougui
Conception et analyse d’algorithmes
5
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Qu’est ce que la complexitØ d’un algorithme ?
C’est l’Øtude de l’e(cid:30)cacitØ comparØe des algorithmes. On mesure :
la taille approximative des donnØes en mØmoire appelØe
complexitØ spatiale,
le temps que prendra l’exØcution de l’algorithme (complexitØ
temporelle).
Exemple : reprØsentation d’une matrice creuse
ReprØsentation par un tableau (cid:224) deux dimensions ou liste cha(cid:238)nØe
contenant les ØlØments non nuls de la matrice + l’information sur le
numØro de ligne et le numØro de colonne ?
Une bonne ma(cid:238)trise de la complexitØ ←→ des applications qui
tournent en un temps prØvisible et sur un espace mØmoire controlØ.
Nour Houda Dougui
Conception et analyse d’algorithmes
6
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ : taille des donnØes
La complexitØ d’un algorithme dØpend de plusieurs facteurs :
La taille des donnØes (cid:224) traiter :
un algorithme opØrant sur une dizaine d’ØlØments ne prend pas
autant de temps que le mŒme opØrant sur un millier de donnØes
→ il faut Øvaluer la taille des donnØes nØcaissaire (cid:224) l’algorithme.
Nour Houda Dougui
Conception et analyse d’algorithmes
7
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ : taille des donnØes
La complexitØ d’un algorithme dØpend de plusieurs facteurs :
La taille des donnØes (cid:224) traiter :
un algorithme opØrant sur une dizaine d’ØlØments ne prend pas
autant de temps que le mŒme opØrant sur un millier de donnØes
→ il faut Øvaluer la taille des donnØes nØcaissaire (cid:224) l’algorithme.
En pratique, on choisit comme taille la ou les dimensions les plus
signi(cid:28)catives :
par exemple, selon que le problŁme est modØlisØ par :
des nombres : ces nombres,
des mots : leurs longueur,
des listes, tableaux : nombre de cases, d’ØlØments,
des matrices m × n : max(m, n), m.n, m + n.
Le choix de telle ou telle structure de donnØes n’est pas anodin
quant (cid:224) l’e(cid:30)cacitØ d’un algorithme.
Nour Houda Dougui
Conception et analyse d’algorithmes
7
une comparaison entre deux valeurs est plus rapide qu’un
accŁs (cid:224) une donnØe dans un (cid:28)chier...
Pour simpli(cid:28)er, on peut faire l’hypothŁse que toutes les opØrations
ont un coßt uniforme (mŒme si cela manque souvent de rØalisme).
Ce coßt est alors constant car il ne dØpend plus de rien.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
Publicité
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ : type des opØrations
Le type des opØrations (cid:224) e(cid:27)ectuer :
Toutes les opØrations e(cid:27)ectuØes par un algorithme ne nØcessitent
pas la mŒme durØe :
une addition est plus rapide qu’une ØlØvation (cid:224) la puissance,
Nour Houda Dougui
Conception et analyse d’algorithmes
8
Pour simpli(cid:28)er, on peut faire l’hypothŁse que toutes les opØrations
ont un coßt uniforme (mŒme si cela manque souvent de rØalisme).
Ce coßt est alors constant car il ne dØpend plus de rien.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ : type des opØrations
Le type des opØrations (cid:224) e(cid:27)ectuer :
Toutes les opØrations e(cid:27)ectuØes par un algorithme ne nØcessitent
pas la mŒme durØe :
une addition est plus rapide qu’une ØlØvation (cid:224) la puissance,
une comparaison entre deux valeurs est plus rapide qu’un
accŁs (cid:224) une donnØe dans un (cid:28)chier...
Nour Houda Dougui
Conception et analyse d’algorithmes
8
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ : type des opØrations
Le type des opØrations (cid:224) e(cid:27)ectuer :
Toutes les opØrations e(cid:27)ectuØes par un algorithme ne nØcessitent
pas la mŒme durØe :
une addition est plus rapide qu’une ØlØvation (cid:224) la puissance,
une comparaison entre deux valeurs est plus rapide qu’un
accŁs (cid:224) une donnØe dans un (cid:28)chier...
Pour simpli(cid:28)er, on peut faire l’hypothŁse que toutes les opØrations
ont un coßt uniforme (mŒme si cela manque souvent de rØalisme).
Ce coßt est alors constant car il ne dØpend plus de rien.
Nour Houda Dougui
Conception et analyse d’algorithmes
8
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
ComplexitØ au pire, au mieux et en moyenne
Soit A un algorithme appliquØ sur des donnØes d ∈ D et soit
T (A, d ) le temps d’exØcution de A en fonction de la donnØe d . Il
existe trois types de mesure de complexitØ pour un algorithme :
la mesure du pire des cas :
TMax (A, D) = Max{T (A, d ), d ∈ D}
la mesure du meilleur des cas :
TMin(A, D) = Min{T (A, d ), d ∈ D}
la mesure de la moyenne : TMoy (A, D) = (cid:80) p(d ).T (A, d )
avec p(d ) la probabilitØ d’avoir la donnØe d
Exemple : Recherche d’un ØlØment dans un tableau.
Nour Houda Dougui
Conception et analyse d’algorithmes
9
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
ComplexitØ au pire, au mieux et en moyenne
Soit A un algorithme appliquØ sur des donnØes d ∈ D et soit
T (A, d ) le temps d’exØcution de A en fonction de la donnØe d . Il
existe trois types de mesure de complexitØ pour un algorithme :
la mesure du pire des cas :
TMax (A, D) = Max{T (A, d ), d ∈ D}
la mesure du meilleur des cas :
TMin(A, D) = Min{T (A, d ), d ∈ D}
la mesure de la moyenne : TMoy (A, D) = (cid:80) p(d ).T (A, d )
avec p(d ) la probabilitØ d’avoir la donnØe d
Exemple : Recherche d’un ØlØment dans un tableau.
Nous avons la propriØtØ suivante entre ces mesures de complexitØ :
TMin(A, D) ≤ TMoy (A, D) ≤ TMax (A, D)
Nour Houda Dougui
Conception et analyse d’algorithmes
9
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
ComplexitØ au pire, au mieux et en moyenne
Soit A un algorithme appliquØ sur des donnØes d ∈ D et soit
T (A, d ) le temps d’exØcution de A en fonction de la donnØe d . Il
existe trois types de mesure de complexitØ pour un algorithme :
la mesure du pire des cas :
TMax (A, D) = Max{T (A, d ), d ∈ D}
la mesure du meilleur des cas :
TMin(A, D) = Min{T (A, d ), d ∈ D}
la mesure de la moyenne : TMoy (A, D) = (cid:80) p(d ).T (A, d )
avec p(d ) la probabilitØ d’avoir la donnØe d
Exemple : Recherche d’un ØlØment dans un tableau.
Nous avons la propriØtØ suivante entre ces mesures de complexitØ :
TMin(A, D) ≤ TMoy (A, D) ≤ TMax (A, D)
On s’intØresse (cid:224) la complexitØ d’un algorithme dans le pire cas.
Nour Houda Dougui
Conception et analyse d’algorithmes
9
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ des algorithmes itØratifs
Dans un programme strictement itØratif, les boucles sont disjointes
ou embo(cid:238)tØes : il n’ y a pas de rØcursivitØ.
Notation : T (n) le nombre d’opØrations ØlØmentaires.
(cid:201)valuation de T (n) (sØquence) → Somme des coßts
(cid:41)
Traitement1 T1(n)
Traitement2 T2(n)
T (n) = T1(n) + T2(n)
Nour Houda Dougui
Conception et analyse d’algorithmes
10
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ des algorithmes itØratifs
(cid:201)valuation de T (n) (embranchement) → Max des coßts
si <condition> Tc (n) alors
Traitement1 T1(n)
sinon
Traitement2 T2(n)
T (n) = Tc (n) + max(T1(n), T2(n))
(cid:201)valuation de T (n) (boucle) → Somme des coßts des passages
tant que <condition> faire
Traitement Ti (n)
(cid:28)n faire
T (n) = (k + 1) ∗ Tc (n) +
k
(cid:88)
i=1
Ti (n)
11
Nour Houda Dougui
Conception et analyse d’algorithmes
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Calcul de complexitØ des algorithmes rØcursifs
(cid:201)valuation de T (n) (fonctions rØcursives) → (cid:201)quation rØcursive
si (n>1) alors
Publicité
fonction FunctionRecursive (n)
(1)
(2)
(3)
(4)
FunctionRecursive ( n
2 )
Traitement(n)
FunctionRecursive ( n
2 )
coßt T ( n
2 )
coßt C (n)
coßt T ( n
2 )
(cid:201)quation rØcursive
T (n) = 2 × T (
n
2
) + C (n)
Nour Houda Dougui
Conception et analyse d’algorithmes
12
Dans le pire cas, quand la table est triØe par ordre inverse,
4 × (n − i) + 3
Dans le meilleur cas, quand le tableau est triØ, on n’exØcute
jamais l’instruction min ← j.
3 × (n − i + 1)
Supposons que, sur les (n − i) tests, la moitiØ est ØvaluØe (cid:224)
vrai. En moyenne, 4 × (n−i)
2 + 3 × (n−i)
2 + 3
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple (extrait du tri par sØlection)
min ← i
→ 1 a(cid:27)ectation
pour j de i + 1 (cid:224) n faire → 1a(cid:27). + 1comp. + (1a(cid:27). + 1comp.)boucle
si A[j] < A[min] alors → (1 comparaison)boucle
min ← j
→ (si test vrai : 1 a(cid:27)ectation)boucle
Nour Houda Dougui
Conception et analyse d’algorithmes
13
Dans le meilleur cas, quand le tableau est triØ, on n’exØcute
jamais l’instruction min ← j.
3 × (n − i + 1)
Supposons que, sur les (n − i) tests, la moitiØ est ØvaluØe (cid:224)
vrai. En moyenne, 4 × (n−i)
2 + 3 × (n−i)
2 + 3
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple (extrait du tri par sØlection)
min ← i
→ 1 a(cid:27)ectation
pour j de i + 1 (cid:224) n faire → 1a(cid:27). + 1comp. + (1a(cid:27). + 1comp.)boucle
si A[j] < A[min] alors → (1 comparaison)boucle
min ← j
→ (si test vrai : 1 a(cid:27)ectation)boucle
Dans le pire cas, quand la table est triØe par ordre inverse,
4 × (n − i) + 3
Nour Houda Dougui
Conception et analyse d’algorithmes
13
Supposons que, sur les (n − i) tests, la moitiØ est ØvaluØe (cid:224)
vrai. En moyenne, 4 × (n−i)
2 + 3 × (n−i)
2 + 3
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple (extrait du tri par sØlection)
min ← i
→ 1 a(cid:27)ectation
pour j de i + 1 (cid:224) n faire → 1a(cid:27). + 1comp. + (1a(cid:27). + 1comp.)boucle
si A[j] < A[min] alors → (1 comparaison)boucle
min ← j
→ (si test vrai : 1 a(cid:27)ectation)boucle
Dans le pire cas, quand la table est triØe par ordre inverse,
4 × (n − i) + 3
Dans le meilleur cas, quand le tableau est triØ, on n’exØcute
jamais l’instruction min ← j.
3 × (n − i + 1)
Nour Houda Dougui
Conception et analyse d’algorithmes
13
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple (extrait du tri par sØlection)
min ← i
→ 1 a(cid:27)ectation
pour j de i + 1 (cid:224) n faire → 1a(cid:27). + 1comp. + (1a(cid:27). + 1comp.)boucle
si A[j] < A[min] alors → (1 comparaison)boucle
min ← j
→ (si test vrai : 1 a(cid:27)ectation)boucle
Dans le pire cas, quand la table est triØe par ordre inverse,
4 × (n − i) + 3
Dans le meilleur cas, quand le tableau est triØ, on n’exØcute
jamais l’instruction min ← j.
3 × (n − i + 1)
Supposons que, sur les (n − i) tests, la moitiØ est ØvaluØe (cid:224)
vrai. En moyenne, 4 × (n−i)
2 + 3 × (n−i)
2 + 3
Nour Houda Dougui
Conception et analyse d’algorithmes
13
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Estimation asymptotique
En complexitØ, on ne veut pas Øvaluer prØcisØment les temps
d’exØcution (d’autant que (cid:231)a dØpend de la machine). On se
contente de trouver des approximations.
Nour Houda Dougui
Conception et analyse d’algorithmes
14
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Estimation asymptotique
En complexitØ, on ne veut pas Øvaluer prØcisØment les temps
d’exØcution (d’autant que (cid:231)a dØpend de la machine). On se
contente de trouver des approximations.
On dit que T est asymptotiquement majorØe (quand n → ∞) par f
et on utilise la notation de Landau O(f (n)).
T (n) = O(f (n)) si ∃c ∃n0 tels que ∀n > n0T (n) ≤ c × f (n)
Nour Houda Dougui
Conception et analyse d’algorithmes
14
nnT(n) = O(f(n))c*f(n)0ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Estimation asymptotique
On dit que T est du mŒme ordre de grandeur que f et on note
Θ(f (n)) quand T (n) = O(f (n)) et f (n) = O(T (n))
T (n) = Θ(f (n)) si ∃c1, c2, n0 tels que
∀n > n0, c1 × f (n) ≤ T (n) ≤ c2 × f (n)
Nour Houda Dougui
Conception et analyse d’algorithmes
15
n0nT(n) = O(f(n))c2f(n)c1f(n)f (n) = n log(n) + 12n + 888 = O(n log(n))
f (n) = 1000n10 − n7 + 2n
1000 = O(2n)
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Publicité
Algorithmes rØcursifs
Exemples
f (n) = n3 + 2n2 + 4n + 2 = O(n3)
(si n ≥ 1 alors f (n) ≤ 8 × n3)
Nour Houda Dougui
Conception et analyse d’algorithmes
16
f (n) = 1000n10 − n7 + 2n
1000 = O(2n)
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemples
f (n) = n3 + 2n2 + 4n + 2 = O(n3)
(si n ≥ 1 alors f (n) ≤ 8 × n3)
f (n) = n log(n) + 12n + 888 = O(n log(n))
Nour Houda Dougui
Conception et analyse d’algorithmes
16
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemples
f (n) = n3 + 2n2 + 4n + 2 = O(n3)
(si n ≥ 1 alors f (n) ≤ 8 × n3)
f (n) = n log(n) + 12n + 888 = O(n log(n))
f (n) = 1000n10 − n7 + 2n
1000 = O(2n)
Nour Houda Dougui
Conception et analyse d’algorithmes
16
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exercice
Nour Houda Dougui
Conception et analyse d’algorithmes
17
O(log n) temps logarithmique : on rencontre une telle
complexitØ lorsque l’algorithme casse un gros problŁme en
plusieurs petits, de sorte que la rØsolution d’un seul de ces
problŁmes conduit (cid:224) la solution du problŁme initiale.
Exemple : recherche dichotomique dans une liste triØe.
O(n) temps linØaire : cette complexitØ est gØnØralement
obtenue lorsqu’un traitement en temps constant est e(cid:27)ectuØ
sur chaque donnØe en entrØe.
Exemple : recherche d’un ØlØment dans une liste.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(1) temps constant : temps d’exØcution indØpendant de la
taille des donnØes (cid:224) traiter.
Nour Houda Dougui
Conception et analyse d’algorithmes
18
O(n) temps linØaire : cette complexitØ est gØnØralement
obtenue lorsqu’un traitement en temps constant est e(cid:27)ectuØ
sur chaque donnØe en entrØe.
Exemple : recherche d’un ØlØment dans une liste.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(1) temps constant : temps d’exØcution indØpendant de la
taille des donnØes (cid:224) traiter.
O(log n) temps logarithmique : on rencontre une telle
complexitØ lorsque l’algorithme casse un gros problŁme en
plusieurs petits, de sorte que la rØsolution d’un seul de ces
problŁmes conduit (cid:224) la solution du problŁme initiale.
Exemple : recherche dichotomique dans une liste triØe.
Nour Houda Dougui
Conception et analyse d’algorithmes
18
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(1) temps constant : temps d’exØcution indØpendant de la
taille des donnØes (cid:224) traiter.
O(log n) temps logarithmique : on rencontre une telle
complexitØ lorsque l’algorithme casse un gros problŁme en
plusieurs petits, de sorte que la rØsolution d’un seul de ces
problŁmes conduit (cid:224) la solution du problŁme initiale.
Exemple : recherche dichotomique dans une liste triØe.
O(n) temps linØaire : cette complexitØ est gØnØralement
obtenue lorsqu’un traitement en temps constant est e(cid:27)ectuØ
sur chaque donnØe en entrØe.
Exemple : recherche d’un ØlØment dans une liste.
Nour Houda Dougui
Conception et analyse d’algorithmes
18
O(n2) temps quadratique ou polynomial : appara(cid:238)t notamment
lorsque l’algorithme envisage toutes les paires de donnØes
parmi les n entrØes.
Exemple : deux boucles imbriquØes.
Remarque : O(n3) temps cubique.
O(2n) temps exponentiel : souvent le rØsultat de recherche
brutale d’une solution.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(n × log n) : l’algorithme scinde le problŁme en plusieurs
sous-problŁmes plus petits qui sont rØsolus de maniŁre
indØpendante. La rØsolution de l’ensemble de ces problŁmes
plus petits apporte la solution du problŁme initial.
Exemple : tri fusion.
Nour Houda Dougui
Conception et analyse d’algorithmes
19
O(2n) temps exponentiel : souvent le rØsultat de recherche
brutale d’une solution.
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(n × log n) : l’algorithme scinde le problŁme en plusieurs
sous-problŁmes plus petits qui sont rØsolus de maniŁre
indØpendante. La rØsolution de l’ensemble de ces problŁmes
plus petits apporte la solution du problŁme initial.
Exemple : tri fusion.
O(n2) temps quadratique ou polynomial : appara(cid:238)t notamment
lorsque l’algorithme envisage toutes les paires de donnØes
parmi les n entrØes.
Exemple : deux boucles imbriquØes.
Remarque : O(n3) temps cubique.
Nour Houda Dougui
Conception et analyse d’algorithmes
19
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Les principales classes de complexitØ
O(n × log n) : l’algorithme scinde le problŁme en plusieurs
sous-problŁmes plus petits qui sont rØsolus de maniŁre
indØpendante. La rØsolution de l’ensemble de ces problŁmes
plus petits apporte la solution du problŁme initial.
Exemple : tri fusion.
O(n2) temps quadratique ou polynomial : appara(cid:238)t notamment
lorsque l’algorithme envisage toutes les paires de donnØes
parmi les n entrØes.
Exemple : deux boucles imbriquØes.
Publicité
Remarque : O(n3) temps cubique.
O(2n) temps exponentiel : souvent le rØsultat de recherche
brutale d’une solution.
Nour Houda Dougui
Conception et analyse d’algorithmes
19
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
(cid:192) Retenir
En pratique :
un algorithme (cid:224) complexitØ exponentielle est inutilisable.
pour n pas trop grand, les algorithmes polynomiaux sont
encore e(cid:30)caces.
Nour Houda Dougui
Conception et analyse d’algorithmes
20
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple 1
Nour Houda Dougui
Conception et analyse d’algorithmes
21
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple 2
Nour Houda Dougui
Conception et analyse d’algorithmes
22
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple 3
Nour Houda Dougui
Conception et analyse d’algorithmes
23
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple 4
Tri par dØnombrement [Seward 1954]
Si on sait que les valeurs sont comprises entre 0 et max (avec max
pas trop grand), on peut trier les valeurs en comptant tout d’abord
le nombre de 0, le nombre de 1, le nombre de 2 ... le nombre de
max en entrØe. Ensuite, il su(cid:30)t de parcourir le tableau (cid:224) nouveau
en indiquant la bonne quantitØ de chaque valeur.
Question 1 : (cid:201)crire cet algorithme. On utilisera un tableau
annexe count oø count[i] indique le nombre de i dans le
tableau initial.
Question 2 : Calculer la complexitØ de cette algorithme.
Question 3 : Discuter cette complexitØ par rapport (cid:224) la borne
thØorique infØrieure.
Nour Houda Dougui
Conception et analyse d’algorithmes
24
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Fonctions rØcursives : Paradigme Diviser pour RØgner
La stratØgie Diviser pour RØgner consiste (cid:224) scinder un problŁme en
sous-problŁmes de mŒme nature sur des instances plus petites, (cid:224)
rØsoudre ces sous-problŁmes, puis (cid:224) combiner les rØsultats obtenus
pour apporter une solution au problŁme posØ.
Nour Houda Dougui
Conception et analyse d’algorithmes
25
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Fonctions rØcursives : Paradigme Diviser pour RØgner
La stratØgie Diviser pour RØgner consiste (cid:224) scinder un problŁme en
sous-problŁmes de mŒme nature sur des instances plus petites, (cid:224)
rØsoudre ces sous-problŁmes, puis (cid:224) combiner les rØsultats obtenus
pour apporter une solution au problŁme posØ.
Il s’agit donc d’une dØmarche essentiellement rØcursive qui donne
donc lieu (cid:224) trois Øtapes (cid:224) chaque niveau de rØcursivitØ :
Nour Houda Dougui
Conception et analyse d’algorithmes
25
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Fonctions rØcursives : Paradigme Diviser pour RØgner
La stratØgie Diviser pour RØgner consiste (cid:224) scinder un problŁme en
sous-problŁmes de mŒme nature sur des instances plus petites, (cid:224)
rØsoudre ces sous-problŁmes, puis (cid:224) combiner les rØsultats obtenus
pour apporter une solution au problŁme posØ.
Il s’agit donc d’une dØmarche essentiellement rØcursive qui donne
donc lieu (cid:224) trois Øtapes (cid:224) chaque niveau de rØcursivitØ :
Diviser : Le problŁme est scindØ en un certain nombre de
sous-problŁmes ;
RØgner : RØsoudre les sous-problŁmes rØcursivement ou, si la taille d’un
sous-problŁme est assez rØduite, le rØsoudre directement ;
Combiner : RØorganiser les solutions des sous-problŁmes en une solution
complŁte du problŁme initial.
Nour Houda Dougui
Conception et analyse d’algorithmes
25
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple : l’Algorithme tri-fusion
L’algorithme de tri-fusion repose sur la dØcomposition suivante :
Nour Houda Dougui
Conception et analyse d’algorithmes
26
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple : l’Algorithme tri-fusion
L’algorithme de tri-fusion repose sur la dØcomposition suivante :
Diviser : On scinde la sØquence de longueur l en 2 sØquences de taille l
RØgner : On rØsout chacune des deux sous-sØquences en utilisant
2 ;
rØcursivement le tri-fusion si elle n’est pas rØduite (cid:224) un ØlØment
et en ne faisant rien sinon ;
Combiner : Fusionner les deux sous-sØquences triØes en une sØquence triØe.
Nour Houda Dougui
Conception et analyse d’algorithmes
26
ComplexitØ des algorithmes
ComplexitØ des problŁmes
Paradigmes de programmation
Les arbres ØquilibrØs
Introduction
DØ(cid:28)nition de la complexitØ algorithmique
Calcul de la complexitØ
Estimation asymptotique
Algorithmes itØratifs
Algorithmes rØcursifs
Exemple : l’Algorithme tri-fusion
Nour Houda Dougui
Concepti...