O-notation
1. Introduction
2. O-notation
3. Opérations
3.1 Somme
3.2 Produit
4. Règles générales
5. Exemple
Introduction
Le temps d ’exécution d'un programme dépend des facteurs
suivants:
- les données du programme
- la qualité du code généré par le compilateur
- la machine (vitesse et nature des instructions)
- complexité de l'algorithme
Le fait que le temps d' exécution dépend des données signifie
que le temps d’exécution pourrait être défini comme une
fonction des données ou comme une fonction de n. ( n étant la
taille des données). Pour les problèmes de tri, il dépend du
nombre d'éléments à trier.
On représente le temps d ’exécution d'un programme avec n
données par T(n)
Introduction
Ex : T(n) = c n2
c est une constante.
( T(n) pourrait être le nombre d'instructions exécutées dans
un ordinateur)
En pratique, le temps moyen est souvent difficile à
dé[Link] utiliserons dans la mesure des
algorithmes le temps dans le
cas le plus défavorable et on mentionne le cas moyen quand
on peut le donner.
Dans l'exemple T(n) = c n2 on peut dire que le temps
d'execution est proportionnel à n2. La constante c n'est pas
spécifiée car elle dépend du compilateur, de la machine, ect . .
.
O-notation ( exemple )
Quand on dit que le temps d'exécution d'un algorithme est
O(n2), cela veut dire qu'il existe une constante c > 0 et une
constante n0 > 0 tel que pour tout n > n0
T(n) <= c n2
Supposons que T(0) = 1, T(1) = 4 et en général
T(n) = (n + 1)2
Montrons que T(n) est O(n2)
O-notation ( exemple )
Il faut donc chercher une constante c > 0 et une constante n0
> 0 telles que Quelque soit n : n > 0 on ait T(n) <= c n2
C'est a dire ( n + 1)2 <= cn2
n2 + 2n + 1 <= c n2
(c-1) n2 - 2n - 1 >= 0
Delta = 4c
Pour c = 4, deux racines 1 et -1/3
Donc pour c = 4 et n0 = 1 on a T(n) <= cn2
(ou (c-1)n2 - 2n - 1 >= 0
Généralisation
On dira que T(n) est O( f(n) )s'il existe c > 0 et n0 > 0 telles que
T(n) <= c f(n) pour tout n >= n0.
un programme dont le temps d ’exécution est O( f(n) ) est un
programme qui a f(n) comme taux de croissance.
on dira aussi que f(n) est une limite supérieure du taux de
croissance de T(n).
Pour spécifier la limite inférieure du taux de croissance de T(n),
on utilisera la notation Omega( g(n) ) qui veut dire: il existe une
constante c > 0 telle que :
T(n) >= c g(n) pour un nombre infini de valeur de n.
Ex : T(n) = n3 + 2n2 est Omega(n3) car pour c = 1 T(n) >= n3 pour
n = 0, 1, 2, .....
Opérations
Somme
Si T1(n) = O ( f(n) ) et T2(n) = O( g(n) ) sont les temps
d'exécution de 2 fragments de programme P1 et P2, alors le
temps d'exécution de P1 suivi de P2 est
T1(n) + T2(n) = O ( max (f(n), g(n) )
Opérations
Somme
Démonstration :
T1(n) = O(f(n) ==> Il existe c1 > 0 et n1 > 0 telles que quelque
soit n > n1 : T1(n) <= C1 f(n)
T2(n) = O(g(n)) ==> Il existe c2 > 0 et n2 > 0 telles que
quelque soit n > n2 : T2(n) <= C2 g(n)
T1(n) + T2(n) <=
c1 f(n) + c2 g(n) pour un n0 = max ( n1, n2)
<= (c1 + c2 ) max ( f(n), g(n) )
donc il existe un c = c1 + c2 et n0 = max(n1,n2)
Opérations
Somme
Exemple
Cette règle peut être utilisée pour calculer le temps d'exécution
d'une séquence d ’étapes d'un programme. Chaque étape peut
être un fragment de programme avec des boucles et des
branchements.
Supposons que nous avons trois étapes dont les temps
d ’exécution sont respectivement O(n2), O(n3) et O(nlogn). alors
le temps d'exécution des deux premières étapes exécutées
séquentiellement est O( max(n2, n3) ) = O (n3). Le temps
d'exécution des trois étapes est O( max(n3, nlogn)) = O(n3). En
général, le temps d'exécution d'une séquence fixe d ’étapes et
celui de l ’étape qui a le plus grand temps d'exécution.
Opérations
Somme
Observation :
si g(n) <= f(n) pour tout n > n0 alors
O( f(n) + g(n) ) = O ( f(n) )
Ex : O(n2 + n ) = O(n2)
Opérations
Produit
Si T1(n) = O( f(n) ) et
T2(n) = O(g(n))
alors
T1(n) * T2(n) = O (f(n) * g(n) )
Opérations
Produit
Démonstration
T1(n) = O(f(n) ==> Il existe c1 > 0 et n1 > 0 telles que quelque
soit n > n1 : T1(n) <= C1 f(n)
T2(n) = O(g(n)) ==> Il existe c2 > 0 et n2 > 0 telles que
quelque soit n > n2 : T2(n) <= C2 g(n)
T1(n) * T2(n) <= c1 * c2 f(n) g(n) pour n >= n0 avec n0 =
max(n1, n2)
Il existe donc un c = c1 * c2 et un n0= max(n1, n2) tels que
T1(n) * T2(n) <= c f(n) g(n). Donc T1(n)*T2(n)=O(f(n)g(n)).
Opérations
Produit
Conséquences : on peut facilement montrer que :
O( c f(n) ) = O( f(n) ) si c > 0.
ex O(n2/2) = O(n2)
Règles générales
[Link] temps d'exécution de chaque affectation, lecture ou écriture
est O(1)
2. Le temps d ’exécution d'une séquence d'instruction est
déterminée par la règle de la somme. C'est donc le temps de la
séquence qui a le plus grand temps d ’exécution.
3. Le temps d'exécution d'une instruction IF est le temps
d ’exécution des instructions exécutées sous condition, plus le
temps pour évaluer la condition. Ce dernier est O(1). Pour une
alternative, on se place dans le cas le plus défavorable.
4. Le temps d ’exécution d'une boucle est la somme du temps
pour évaluer le corps et du temps pour évaluer la condition. ce
dernier prend O(1). Souvent ce temps est le produit du nombre
d'itérations de la boucle par le plus grand temps possible pour
une exécution du corps. Quelquefois le nombre d'itérations n'est
pas connu précisément. Ce qui rend difficile sinon impossible la
détermination du temps.
Exemple
Procedure bubble ( var A : array(1..N) of integer)
var i, j, temp : integer;
begin
(1) for i:= 1 to n-1 do
(2) for j := n downto i+1 do
(3) if A(j-1) > A(j)
then begin
(4) temps := A(j-1)
(5) A(j-1) := A(j)
(6) A(j) := temp
end;
end;
Soit n le nombre de données à trier.
Exemple
Chaque instruction d'affectation prend une valeur constante
du temps indépendante de n. Donc les instructions (4) (5) et
(6) occupent chacun O(1). ( C'est a dire il existe c > 0 et n0 > 0
telles que quelque soit n > n0 T(n) <= c.1 ; en d'autres termes
on peut toujours trouver une constante c telle que le temps
d'exécution de l'affectation soit inférieur à c)
D'après la règle de la somme le temps d'exécution de (4) (5)
et (6) est O( max(1, 1, 1) ) = O(1).
Exemple
Considérons maintenant les instructions conditionnelle et
répétitives en allant du niveau le plus interne vers le niveau le
plus externe.
Pour l'instruction IF, le test de la condition exige O(1).
L'exécution des 3 affectations dépend de la valeur du test.
puisque nous recherchons le temps d'exécution dans le cas le
plus défavorable, donc l'instruction IF prend aussi O(1).
Exemple
Analysons maintenant la boucle (2) à (6). La règle générale
pour une boucle est que le temps d'exécution est la somme du
temps dépensé par l'exécution du corps de la boucle pour
chaque itération. le corps de la boucle prend O(1) pour
chaque itération (incrémention de l'index, test des limites,
branchement vers le début de la boucle). Le nombre
d'itérations est n-i donc d'après la règle du produit:
corps : O(1)
boucle : O(n-i)
Le temps dépensé de (2) a (6) est O( (n-i)*1 ) = O (n-i).
Exemple
Analysons la boucle la plus externe qui contient toutes les
instructions exécutables du programme. L'instruction 1 est
exécutée n-1 fois. Donc le temps total d'exécution du
programme est limite par
Somme des (n-i) pour i=1, n-1 = n(n-1)/2= n2-n/2 qui est
O(n2).
Exemple
Autre façon de procéder :
Dans la boucle (1) (6)
corps : O(n-i) ou O(n) (résultat précédent)
boucle : O(n-1) ou O(n)
Règle du produit : O(n.n) = O(n2)