Ch3: Outils mathématiques pour

la complexité algorithmique
Sommaire

 Notations asymptotiques
 Propriétés des notations asymptotiques
 Fonctions classiques
 Sommations
 Récurrences de partitions
Notations asymptotiques

 Notation grand O :
– Une fonction g(n) est une borne
supérieure asymptotique de f(n), si et
seulement :
( C  0), ( n0  0) : f(n)  Cg(n), ( n  n0).
– On note alors : f(n) = O(g(n)).
Notations asymptotiques

 Exemple :
– f(n) = n3 + 5n2 - 7n + 18.
– g(n) = n3.
– On a : f(n) = O(g(n)).
– En effet : comme 5n2  5n3, -7n  7n3 et 18  18n3,
 n  1, alors :
 f(n) = n3 + 5n2 - 7n +18  n3 + 5n3 + 7n3 +18n3.
 f(n)  31n3 = 31g(n).
 ( C = 31  0), ( n0 = 1  0) : f(n)  Cg(n), ( n 
n0).
Notations asymptotiques

 Notation grand  :
– Une fonction g(n) est une borne inférieure
asymptotique de f(n), si et seulement :
( C  0), ( n0  0) : f(n)  Cg(n), ( n  n0).
– On note alors : f(n) = (g(n)).
Notations asymptotiques

 Exemple :
– f(n) = 5n2log(n) + 1.
– g(n) = n.
– On a : f(n) = (g(n)).
– En effet :
 5n2  5n, ( n  0).
 log(n)  1, ( n  e = 2.7182883).
 f(n) = 5n2log(n) + 1  5n + 1  4n, ( n  3).
 f(n)  4g(n), ( n  3).
 ( C = 4  0), ( n0 = 3  0) : f(n)  Cg(n), ( n 
n0).
Notations asymptotiques

 Notation grand  :
– Deux fonctions f(n) et g(n) ont même ordre
de grandeur asymptotique, si et
seulement :
( C1  0), ( C2  0), ( n0  0) :
C1g(n)  f(n)  C2g(n), ( n  n0).
 On note alors : f(n) = (g(n)).
Notations asymptotiques

 Exemple :
– f(n) = 3n2 + 2n + 1.
– g(n) = n2.
– On a : f(n) = (g(n)).
– En effet :
 3n2 + 2n + 1  3n2 + 2n2 + n2 = 6n2 ( n  1).
 3n2 + 2n + 1  2n2 ( n  0).
 ( C1 = 2  0), ( C2 = 6  0), ( n0 = 1  0) :
C1g(n)  f(n)  C2g(n), ( n  n0).
Notations asymptotiques

 Remarques :
– f(n) = (g(n))  f(n) = O(g(n)) et f(n) =
(g(n)).
– La notation « f(n) = O(g(n)) » (resp (g(n)),
ou (g(n))) n’est pas une égalité
mathématique.
– Ce sont des conventions d’écriture.
Propriétés des notations
asymptotiques

 Réflexivité :
– f(n) = O(f(n)).
– f(n) = (f(n)).
– f(n) = (f(n)).
 Symétrie de  :
– f(n) = (g(n))  g(n) = (f(n))
 Symétrie transposée de O et  :
– f(n) = O(g(n))  g(n) = (f(n))
Propriétés des notations
asymptotiques

 Transitivité :
– f(n) = O(g(n)) et g(n) = O(h(n))  f(n) =
O(h(n)).
– f(n) = (g(n)) et g(n) = (h(n))  f(n) =
(h(n)).
– f(n) = (g(n)) et g(n) = (h(n))  f(n) =
(h(n)).
Fonctions classiques

 Partie entière :
– Partie entière supérieur :
 x : plus petit entier supérieur ou égal à x.
 Exemples :
– -2 = -2; 2 = 2; 2.01 = 3; 2.95 = 3;
 x = x  x  Z.
 x  x  x + 1; ( x  IR).
 n = (n).
Fonctions classiques

 Partie entière :
– Partie entière inférieur :
 x : plus grand entier inférieur ou égal à x.
 Exemples :
– -2 = -2; 2 = 2; 2.01 = 2; 2.99 = 2;
 x = x  x  Z.
 x - 1  x  x; ( x  IR).
 n = (n).
Fonctions classiques

 Fonction polynomiale :
– Fonction polynomiale asymptotiquement
positive de degré d :
 f(n) = adnd + … + a2n2 + a1n + a0, avec la
condition ad  0.
 Il résulte que : f(n)  0 à partir d’un certain rang
n0 .
– Théorème :
 f(n) = adnd + … + a1n + a0 = (nd).
Fonctions classiques

 Preuve du théorème :
– f(n) = O(nd).
 f(n)  |f(n)|  |ad|nd + … + |a1|n + |a0|; ( n  0)
 f(n)  |ad|nd + … + |a1|nd + |a0|nd; ( n  1)
 f(n)  (|ad| + … + |a1| + |a0|)nd; ( n  1)
 f(n)  Cnd; (n1) où C = |ad| + … + |a0|  0.
Fonctions classiques

 Preuve du théorème :
– f(n) = (nd).
 f(n)  (1/2)adnd; à partir d’un certain rang.
 En effet, f(n) - (1/2)adnd = (1/2)adnd + … +
a1n + a0; est une fonction polynomiale
asymptotiquement positive, donc > 0 à
partir d’un certain rang n0.
 f(n)  Cnd; ( n  n0) où C = (1/2)ad  0.
Fonctions classiques

 Fonction exponentielle :
– f(n) = an; où a  1 (a c’est la base de
l’exponentielle).
– Lim(nd / an) = 0, pour tout a > 1 et d réel.
– Une fonction exponentielle quelconque
avec une base > 1 croît plus vite que
n’importe quelle fonction polynomiale.
Fonctions classiques

 Fonction logarithmique :
– f(n) = logb(n) = log(n) / log(b); où b  0 (b
c’est la base du logarithme).
– Lim(logba(n) / nd) = 0, pour tout a > 0, b > 0
et d > 0.
– Une fonction polynomiale (asymp.
positive) croît plus vite que n’importe
quelle fonction logarithmique.
Fonctions classiques

 Fonction factorielle :
– n! = 1  2  …  n.
– 0! = 1! = 1.
– Formule de Stirling :
n! = sqrt(2n)  (n/e)n(1 + (1/n)).
Fonctions classiques

 Comparaison des fonctions classiques :

 Définition :
– Une récurrence de partitions est une
équation de récurrence de la forme :
 T(1) = (1);
 T(n) = aT(n/b) + (f(n)); où a  0 et b  1.
Récurrences de partitions

 Théorème fondamental :
– Si T est une fonction croissante et si
 T(1) = (1);
 T(n) = aT(n/b) + (nd); où a  0, b  1 et d  0.
– Alors :
 T(n) = (nd); si d  logb(a).
 T(n) = (nd  logb(n)); si d = logb(a).
 T(n) = (nlogb(a)); si d  logb(a).
Récurrences de partitions

 Exemple 1 :
– T(n) = 2T(n/2) + n3
 a = 2; b = 2; d = 3.
 logb(a) = 1  3 = d.
 T(n) = (n3).
Récurrences de partitions

 Exemple 2 :
– T(n) = 9T(n/3) + n2
 a = 9; b = 3; d = 2.
 logb(a) = 2 = d.
 T(n) = (n2log3(n)).
Récurrences de partitions

 Exemple 3 :
– T(n) = 4T(n/2) + n
 a = 4; b = 2; d = 1.
 logb(a) = 2  1 = d.
 T(n) = (nlog2(4)) = (n2).