[PDF] Complexité dun algorithme Il comprend deux boucles imbriqué

2nest de plus petite complexité quen:O(log2n) =O(10n2)

Complexit

´e - p.11/25

Propriétés

Réflexivité:

g=O(g)Transitivité :

sif=O(g)etg=O(h)alorsf=O(h)Produit par un scalaire :O(λf) =O(f),λ >0.Somme et produit de fonctions :

O(f)+O(g)=O(max{f,g})O(f).O(g)=O(f.g)

Complexit

´e - p.12/25

Complexité d'une boucle

pouri←1ànfaire s finpour avec s=O(1).

Temps de calcul des:Ts=CNombre d'appels des: nTemps de calcul total :T(n) =nTs=O(n)Complexité :O(n)

Complexit

´e - p.13/25

Boucles imbriquées

Théorème 1La complexité depboucles imbriquées de 1 ànne contenant que des instructions élémentaires est en O(np)

Preuve:

vrai pourp= 1,supposons la ppt vrai à l'ordrep. Soit : pouri←1ànfaire instruction finpour

Complexit´e - p.14/25

Boucles tant que

h←1 h←2*h fintantque

Test, multiplication, affectation :O(1):T=CNombre d'itérations :log2(n).Temps de calcul :T(n) =Clog2(n) =O(log2(n))

Complexit

´e - p.15/25

Complexité d'un algorithme récursif (1)

Soit l'algorithme :

fonctionfactorielle(n: Naturel) :Naturel début sin = 0alors retourner1 sinon retournern*factorielle(n-1) finsi fin

Complexit

´e - p.16/25

Complexité d'un algorithme récursif (2)

c

1test,c2multiplication.

T(0)=c1T(n)=c1+c2+T(n-1)

?T(n) =nc2+ (n+ 1)c1

SoitC= 2max{c1,c2}

Complexité enO(n).

Les calculs de complexité d'algorithmes récursifs induisent naturellement des suites.

Complexit

´e - p.17/25

Algorithmes récursifs enO(log2(n))(1)

Théorème 2Soient,debut,finetn=fin-debuttrois entiers. La complexité de l'algorithme ci dessous est enO(log2(n)). procéduref(debut,fin)

Déclaration Entiermilieu

début milieu←debut+fin

2sifin-milieu>1 et milieu-debut>1alors

s sinon sitestalors f (debut,milieu) sinon f (milieu,fin) finsi finsi fin

Complexit´e - p.18/25

Algorithmes récursifs enO(log2(n))(2)

Tests, s :O(1)

T(n) =T(n

2) +C T(n

2) =T(n

4) +C...=...

T(1) =T(0) +C

T(n) =T(0) +Clog2(n)

Complexit´e - p.19/25

Algorithmes récursifs enO(nlog2(n))(1)

procéduref(debut,fin)

Déclaration Entiermilieu

début milieu←debut+fin

2sifin-milieu>1 et milieu-debut>1alors

s

1sinon

pouri←1ànfaire s

2finpourf(début,milieu)f(milieu,fin)

finsi fin

Complexit

´e - p.20/25

Algorithmes récursifs enO(nlog2(n))(2)

Tests, s :O(1)Boucle :O(n).

T(n) =n+ 2T(n

2) 2T(n 2) n+ 4T(n

4)...=...

2 p-1T(2) =n+ 2pT(1)

T(n) =n?p+ 2p?T(1)

avecp= [log2(n)]

On a de plus:O(nlog2(n) +nT(1)) =O(nlog2(n))

Complexit´e - p.21/25

Principales complexités

O(1): temps constant,O(log(n)): complexité logarithmique (Classe L),

O(n): complexité linaire

(Classe P), O(nlog(n))O(n2),O(n3),O(np): quadratique, cubique,polynomiale (Classe P),

O(pn)complexité exponentielle

(Classe

EXPTIME)".

O(n!)complexité factorielle.

Complexit

´e - p.22/25

Influence de la complexité

n→2n. O(1)

O(log2(n))

O(n)

O(nlog2(n))

O(n2) O(n3) O(2n) t t+ 1 2t

2t+ 2n

4t 8t t2 1 log2(n) n nlog2(n) n2 n3 2n n= 102

1μs

6μs

0.1ms 0.6ms 10ms 1s

4×1016a

n= 103

1μs

10μs

1ms 10ms 1s

16.6min

n= 104

1μs

13μs

10ms 0.1s 100s
11,5j n= 105

1μs

17μs

0.1s 1.6s 2.7h 32a
n= 106

1μs

20μs

1s 19.9s 11,5j

32×103a

∞Complexit´e - p.23/25

Limites de la complexité

La complexité est un résultat asymptotique : un algorithme enO(Cn2)peut être plus efficace qu'un algorithme enO(C?n)pour de petites valeurs den siC?C?,Les traitements ne sont pas toujours linéaires?Il ne faut pas supposer d'ordres de grandeur entre les différentes constantes.

Complexit

´e - p.24/25

Conseils

Qualités d'un algorithme :

1. Maintenable (facile à comprendre, coder, déboguer),

2. Rapide

Conseils :

1. Privilégier le point 2 sur le point 1 uniquement si on gagne en complexité.

2. "ce que fait» l'algorithme doit se lire lors d'une lecture rapide : Une idée

par ligne. Indenter le programme.

3. Faire également attention à la précision, la stabilité et la sécurité.

La rapidité d'un algorithme est un élément d'un tout définissant les qualités de celui-ci.

Complexit

´e - p.25/25

quotesdbs_dbs28.pdfusesText_34