Algorithmique
Cours 2 : Notations de Landau, complexité pire cas
ROB3 – année 2014-2015
Complexité d’un algorithme
La complexité (temporelle) d’un algorithme est une évaluation du
nombre d’instructions élémentaires pour une exécution de
l’algorithme.
Elle est exprimée en fonction de la taille de codage des paramètres de
l’algorithme, et en utilisant les notations de Landau (ordres de
grandeur).
Complexité pire cas : on évalue le nombre d’instructions dans le pire
des cas (borne supérieure) ;
Complexité meilleur des cas : on évalue le nombre d’instructions dans
le meilleur des cas (borne inférieure) ;
On identifie généralement le complexité d’un algorithme avec son pire
cas.
Taille d'une instance d'un problème
Plusieurs définitions de la taille d'une instance sont possibles dans la
mesure où une même instance peut s’énoncer de différentes
manières.
En toute rigueur, l’efficacité d’un algorithme devrait prendre en compte
non pas l’instance mais sa représentation fournie en entrée de
l’algorithme.
Cependant la plupart des représentations raisonnables d’une instance
conduisent à des tailles similaires. Plutôt que de formaliser cette
notion, nous la préciserons pour chaque problème traité.
Exemples :
Multiplication de deux entiers sur n bits → taille : n
Tri d'un tableau A[1...n] → taille : n
etc.
Complexité pire cas : motivations
Evaluer le temps d’exécution d’un algorithme en fonction de la
longueur de l’énoncé.
Comparer les performances de différents algorithmes résolvant
le même problème.
Evaluer la taille maximale des énoncés qu’un algorithme peut
traiter.
Mesure du temps indépendante des machines → on compte le
nombre d’instructions.
Evaluation de la complexité
On est souvent incapable de calculer la complexité exacte TA(n) d’un
algorithme A.
Ce qui est important, c’est le comportement de TA(n) pour les grandes
valeurs de n.
On cherche donc à encadrer le taux de croissance de TA(n) pour n
suffisamment grand.
Notations de Landau: , O et Ω
relations dans l’ensemble des fonctions de N dans N.
Soient f et g deux fonctions de N dans N.
f O(g)
s’il existe une constante D positive
et un entier n0 tels que:
n > n0, f(n) ≤ Dg(n).
f Ω(g)
s’il existe une constante C
positive et un entier n0 tels que:
n > n0, Cg(n) ≤ f(n).
f (g)
s’il existe 2 constantes C et D positives et un entier n0 tels que:
n > n0, Cg(n) ≤ f(n) ≤ Dg(n).
Exemples : 100n2 + 4nlog2(n) O(n2) ; 2n + n10 O(2n) ;
Il n’existe aucun entier K tel que 2n O(nK)
Quelques règles utiles
Les quelques règles suivantes permettent de simplifier les
complexités en omettant des termes dominés :
● Les coefficients peuvent être omis : 14n2 devient n2
● na domine nb si a > b : par exemple, n2 domine n
● Une exponentielle domine un polynôme : 3n domine n5 (cela domine
également 2n)
● De même, un polynôme domine un logarithme : n domine (log n)3.
Cela signifie également, par exemple, que n2 domine n log n.
Exemple : complexité de TRI_INS
Supposons que seules les comparaisons de 2 entiers du tableau
soient comptées.
Procédure TRI_INS(T : tableau d’entiers, n : entier);
# comparaisons
Pour i de 2 à n faire ------------------------------ 0
z:=T[i]; k:=i-1; ----------------------------- 0
Tantque k>0 et T[k]>z faire --------------------- N2+N3+…+Nn
T[k+1]:=T[k]; k:=k-1 ---------------------- 0
Fintantque;
T[k+1]:=z; ----------------------------------------- 0
Finpour.
Exemple : un déroulement de TRI_INS
Début d'itération Fin d'itération
i=2 9 6 1 4 8 6 9 1 4 8
i=3 6 9 1 4 8 1 6 9 4 8
i=4 1 6 9 4 8 1 4 6 9 8
i=5 1 4 6 9 8 1 4 6 8 9
Déterminer la complexité « en » de TRI_INS
Comme Ni≤i-1, on a: TRI_INS(n) ≤ 1/2 n(n-1).
Donc TRI_INS(n) = O(n2).
Si les éléments du tableau sont initialement rangés dans l’ordre
décroissant strict :
on a Ni=i-1 pour tout i de 2 à n.
Or pour un énoncé quelconque de taille n, on a :
Ni≤i-1 pour i de 2 à n,
Il en résulte que : TRI_INS(n)= 1/2 n(n-1).
L’algorithme TRI_INS est donc de complexité (n2).
Rappel de la séance précédente
● On s'est intéressé au comptage des lapins, via le calcul
du nème terme de la suite de Fibonacci :
F0 = 1
F1 = 1
Fn = Fn-1 + Fn-2
● On a vu deux algorithmes pour ce problème :
– Algorithme Fib1 de complexité O(20,694n)
– Algorithme Fib2 de complexité O(n2)
Algorithme Fib3 matriciel
On écrit F1=F1 et F2=F0+F1 en matriciel :
où F0=0 et F1=1. De même,
Et plus généralement
Calcul de Fn : élever la matrice à la puissance n.
Algorithme Fib3 matriciel
● Le problème se réduit à calculer :
● Réalisable en O(log2 n) produits matriciels (plus
précisément, mises au carré) :
Analyse de la complexité de Fib3
● A chaque itération, la mise au carré requiert :
– 4 additions, On va s'intéresser aux nombres d'opérations
élémentaires induites par les multiplications
– 8 multiplications.
● Initialement, chaque nombre dans la matrice tient sur
1 = 20 bit.
● A la ke itération de Fib3, il tient sur 2k bits (les
longueurs sont doublées à chaque itération).
Analyse de la complexité de Fib3
● A la ke itération (mise au carré) de Fib3, une
composante de la matrice tient sur 2k bits.
● Supposons que la multiplication de deux nombres
de n bits requiert O(na) opérations élémentaires
● Le nombre d'opérations élémentaires induites par
les multiplications au cours des log2n itérations est :
(somme des (log2n +1) termes d'une suite
géométrique de premier terme 1 et de raison 2a)
Analyse de la complexité de Fib3
En conclusion : pour savoir si Fib3 est plus
rapide que Fib2, il faut s'intéresser à la
complexité de la multiplication de deux
nombres de n bits. Si on peut le faire avec une
complexité moindre que O(n2), alors Fib3 est
plus rapide.
Multiplication
Intuitivement plus difficile qu'une addition… Une analyse permet de quantifier cela.
[13] 1 1 0 1
[11] 1 0 1 1
----------------------------------------------
1 1 0 1
1 1 0 1
0 0 0 0
1 1 0 1
--------------------------------------------------------------------
[143] 1 0 0 0 1 1 1 1
Pour multiplier deux nombres de n bits : créer un tableau de n sommes
intermédiaires, et les additionner. Chaque addition est en O(n)… un total en O(n2).
Il semble donc que l'addition est linéaire, alors que la multiplication est quadratique.
Doit-on en conclure que Fib3 ne fait pas mieux que Fib2 ?
Multiplication égypto-franco-russe
● Il existe d'autres façons de multiplier !
● La paternité de la méthode ci-dessous varie selon
les sources (d'où le titre du transparent) :
11 13
5 26 Répéter
Diviser par 2 le nb de gauche
2 52 Multiplier par 2 le nb de droite
Jusqu'à ce que nb de gauche = 1
1 104 Retourner la somme des nbs de
----------------------------- la colonne de gauche qui sont
face à des nbs impairs
143
Réécrit en binaire...
1011 1101
101 11010 Multiplier par 2 un nombre
binaire : insérer un bit 0 en
10 110100 fin de représentation
1 1101000
Diviser par 2 un nombre
------------------------------ binaire : supprimer le
dernier bit de la
0001111 représentation
Hum... ça ne rappelle pas quelque chose ?
Comparaison des deux méthodes
1011 1101
101 11010
10 110100
Les deux méthodes réalisent 1 1101000
en fait les mêmes calculs ! ------------------------------------
→ même complexité
10001111
[13] 1 1 0 1
[11] 1 0 1 1
----------------------------------------------
1 1 0 1
1 1 0 1 0
0 0 0 0
1 1 0 1 0 0 0
--------------------------------------------------------------------
[143] 1 0 0 0 1 1 1 1
Une multiplication récursive
fonction multiplier(x,y)
Entrée: Deux entiers x et y sur n bits
Sortie: Leur produit
si x = 1 retourner y
z = multiplier(x/2,y) (division entière)
si x est pair retourner 2z
sinon retourner y+2z
Analyse de cet algorithme en exercice
Une multiplication récursive
Remarque importante : cet algorithme récursif
peut en fait se voir comme une autre formulation
de la multiplication égypto-franco-russe...
MAIS c'est formateur de le voir en exercice.
Néanmoins, cela ne fait pas avancer le
comptage des lapins, car Fib3 n'est
toujours pas de meilleure complexité que
Fib2...