Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité des algorithmes

P. Njionou Sadjang?
pnjionou@[Link]

? University of Douala

Ecole Nationale Supérieure Polytechnique, Douala

Douala, Février 2023

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

1 Outils mathématiques

2 Evaluation des performances

3 Complexité Définition et Motivation

4 Calcul de complexité
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

1 Outils mathématiques

2 Evaluation des performances

3 Complexité Définition et Motivation

4 Calcul de complexité
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

1 Outils mathématiques

2 Evaluation des performances

3 Complexité Définition et Motivation

4 Calcul de complexité
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

1 Outils mathématiques

2 Evaluation des performances

3 Complexité Définition et Motivation

4 Calcul de complexité
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

DAY 1
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

(Uk )k ∈N notera la suite de terme général Uk , k ∈ N.

q
∑ Uk : somme des termes Uk où k est tel que p ≤ k ≤ q.
k =p
On va adopter la convention suivante:
Lorsque la p > q, la somme vaut 0.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

Opérateurs usuels:
+: addition
−: soustraction
×: multiplication
/: division
<: strictement inférieur
≤: inférieur ou égal
mod : modulo
bx c: partie entière inférieur du réel x: le plus grand entier ≤ x
dx e: partie entière supérieure du réel x: le plus petit entier ≥ x.
n !: la factorielle de n:
n
n ! := ∏i = 1×2×3×...×n
i =1
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

Pour tout réel x et pour tout entier n:

bx c = n ⇐⇒ n ≤ x < n + 1;
dx e = n ⇐⇒ n − 1 < x ≤ n;
bx + n c = bx c + n;
dx + n e = dx e + n.
n = bn /2c + dn /2e.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

Pour tout réel x, pour tout entier n:

bx c < n ⇐⇒ x < n
n ≤ bx c ⇐⇒ n ≤ x
dx e ≤ n ⇐⇒ x ≤ n
n < dx e ⇐⇒ n < x.
Pour tous réels x et y:
bx c + by c ≤ bx + y c ≤ bx c + by c + 1
dx e + dy e − 1 ≤ dx + y e ≤ dx e + dy e.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

Fonction Exponentielle et Logarithme
exp(a ) exp(b ) = exp(a + b )
1
exp(−a ) =
exp(a )
exp(x ) = y ⇐⇒ x = ln(y) (pour y > 0
exp(ln(y)) = y ln(exp(x )) = x.
ln(uv ) = ln(u ) + ln(v )
 
1
ln = − ln(u )
u
On en déduit (au moins pour n entier):

a n = exp(ln(a ))n = exp(n ln(a )).

On définit donc, pour x > 0 et a quelconque

x a := exp(x ln(a )).

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Outils mathématiques

Outils mathématiques: Analyse élémentaire

Différents logarithmes
ln Logarithme népérien (ou naturel), de base e.
ln x
loga Logarithme de base a: loga (x ) = .
ln a
log fonction logarithme sans base précise, à une
constante multiplicative près
ln x
log2 logarithme binaire (de base 2): loga (x ) = .
ln a

a x = y ⇐⇒ x = loga (y)
2x = y ⇐⇒ x = log2 (y)
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Temps de calcul

Temps de calcul

Sur les machines actuelles, le temos pris par un calcul est très
difficile à prévoir, avec une forte composante aléatoire:
traduction (interprétation, compilation) code de haut niveay vers
code de bas niveau, microcode
forte dépendance à l’environement (mémoire, système
d’exploitation, ...)
nombreuses optimisations qui dépendent de l’historique
(cache,...).

Dans la suite on travaille avec un modèle de machine simplifiée.

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexité

Un algorithme à partir d’une donnée établit un résultat.

La taille de la donnée est mesurée par un entier n.
complexité temporelle:
C’est une fonction de n qui mesure le temos de calcul pour une
donnée de taille n.
Complexité en mémoire:
une fonction de n qui mesure la place mémoire utilisée pour le
calcul sur une donnée de taille n.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Dans le pire des cas: donne une borne supérieure sur le temps
de calcul pour toutes les données de taille n.
En moyenne: fait la moyenne des temps de calculs pour toutes
les données de taille n.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Peut on vraiment mesurer le temps de calculs?

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Peut on vraiment mesurer le temps de calculs?

NON, car le temps de calcul dépend de la machine
On évalue le nombre d’opérations "élémentaires" faites (addition,
multiplications, etc.)
On obtient donc une estimation du temps de calcul à une
constante multiplicative près
Dans cette estimation, on ne considère que le terme dominant.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Définitions
On dit que f est dominée par g et on note f = O (g ) lorsque

∃n0 ∈ N, ∃c > 0.∀n ∈ N, n ≥ n0 =⇒ |f (n )| ≤ cg(n ).

On dit que f est du même ordre de grandeur que g et l’on note

f Θ(g ) lorsque f = O (g ) et g = O (f ).
On dit que f est négligeable devant g et on note f = o (g )
f (n )
lorsque tend vers 0 quand n tend vers l’infini.
g (n )
f (n )
On dit que f est équivalente à g lorsque tend vers 1
g (n )
lorsque n tend vers l’infini.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Exercice
A t’on les implications?
(f est négligeable devant g) =⇒ (f est dominée par g)
(f est équivalente à g) =⇒ (f est du même ordre de grandeur
que g)
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Remarque:
Hormis pour l’équivalence, ces notions sont indépendantes des
constantes multiplicatives non nulles.
Par exemple:
Si f est négligeable devant g, alors λf est négligeable devant λ0 g
pour tous réels λ, λ0 non nuls.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Exercice
Soit P (n ) un polynôme en n.
Pour quelles valeurs de p a-t-on P (n ) = O (n p ).
Pour quelles valeurs de p a-t-on P (n ) = Θ(n p )?
Montrer que pour tout entier k, on a:
n
∑ i k = Θ (n k +1 ).
i =0
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Complexités temporelles

Exercice
Soient les fonctions

f1 (n ) = n f5 (n ) = n n
n
f2 (n ) = 2 f6 (n ) = log(n )
2
f3 (n ) = n f7 (n ) = n !
f4 (n ) = 2n f8 (n ) = nlog(n )

Pour chaque couple (i , j ), dire si on a fi = o (fj ), fi = O (fj ), fi = Θ(fj ).

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

Thank you for your attention!

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexités

DAY 2
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Pour la plupart des problèmes il existe un gramd nombre

d’algorithmes possibles. Comment choisir le meilleur? quels sont les
différents degrés de complexité que l’on peut rencontrer?

Définition
La complexité d’un algorithme est le nombre d’opérations
élémentaires qu’il doit effectuer pour mener à bien un calcul en
fonction de la taille des données d’entrées.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Nous avons donc deux éléments à prendre en compte:

la taille des données;
le temps de calcul.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

La taille des données

La taille des données (ou des entrées) va dépendre du codage de ces
entrées. On choisit comme taille la ou les dimensions les oplus
significatives.
Par exemple, en fonction du problème, les entrées et leur taille
peuvent être:
des éléments: le nombre d’éléments
des nombres: nombre de bit nécessaires à la représentation de
ceux là;
des polynômes: le degré, le nombre de coefficients non nuls;
des matrices: m × n: max(m , n ), m .n, m + n;
des graphes: nombre de sollets, npombre d’arcs, produit des
deux;
des listes, tableaux, fichiers: nombre de cases, d’éléments;
des mots: leur longueur.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

le temps de calcul
Le temps de calcul d’un programme dépend de plusieurs éléments:
la quantité de données bien sûr;
mais aussi de leur encodage
de la qualité du code engendré par le compilateur;
de la nature et la rapidité des instructions du langage;
de la qualité de la programmation
et de l’efficacité de l’algorithme
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Nous ne voulons pas mesurer le temps de calcul par rapport à toutes

ces variables. Mais nous cherchons à calculer la complexité des
algorithmes qui ne dépendra ni de l’ordinateur, ni du langage utilisé,
ni du programmeur, ni de l’implémentation. Pour cela, nous allons
nous mettre dans le cas où nous utilisons un ordinateur RAM
(Random Access Machine):
ordinateur idéalisé;
mémoire infinie;
accès à la mémpire en temps constant
généralement à un processeur unique (pas d’opération
simultanées).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Pour connaître le temps de calcul, nous choisissons une opération

fondamentale et nous calculons le nombre d’opérations
fondamentales exécutées par l’algorithme.
Opérations fondamentale

C’est la nature du problème qui fait que certaines opérations

deviennent plus fondamentales que d’autres dans un algorithme.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Par exemple:

Problème Opération fondamentale

Recherche d’un élément dans une liste Comparaison
Tri d’une liste, d’un fichier,... comparaison, déplacements
Multiplication des matrices réelles Multiplication et additions
Addition des entiers binaires opération binaire
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Complexité Définition et Motivation

Coût des opérations

Coût de base
Pour la complexité en temps, il existe plusieurs possibilités:
Première solution: calculer (en fonction de n) le nombre
d’opérations élémentairtes (addition, comparaison, affectation,...)
requises par l’exécution puis le multiplier par le temps moyen de
chacune d’elle;
pour un algorithme avec essentiellement des calculs numériques,
compter les opérations coûteuses (multiplications, racine,
exponemtielle,...);
sinon compter le nombre d’appels à l’opération la plus fréquente.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Cpmplexité asymptotique

Souvent c’est le principe de l’algorithme que l’on veut juger, et non les
détails de l’implémentation. On veut donc abstraire de tous les
facteurs constants ; de toute façon, ils changeront d’une
implémentation à une autre, et d’une machine à une autre. Pour ne
retenir que l’essentiel, on regroupe les fonctions suivant leur « ordre
de grandeur » :
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Cpmplexité asymptotique

Définition
Soit g : N → R+ une fonction positive. On définit alora les classes suivantes:

1 O (g ) = {f : N → R+ |∃C > 0, ∃n0 ∈ N, ∀n ≥ n0 : f (n ) ≤ Cg (n )}.

Ce sont les fonctions qui croissent au plus aussi vite que g (finalement
majorées par Cg).
2 Ω(g ) = {f : N → R+ |∃c > 0, ∃n0 ∈ N, ∀n ≥ n0 : f (n ) ≥ Cg (n )}.
Ce sont les fonctions qui croissent au moins plus vite que g (finalement
minorées par cg).
3 Θ(g ) = O (g ) ∩ Ω(g ) = {f : N → R+ |∃c , C > 0, ∃n0 ∈ N, ∀n ≥ n0 :
cg (n ) ≤ f (n ) ≥ Cg (n )}.
Ce sont les fonctions qui croissent aussi vite que g (qui ont même ordre
de grandeur).
4 o (g ) = {f : N → R+ |, f (n )/g (n ) → 0 pour n → ∞}.
Ce sont les fonctions qui croissent moins vite que g (qui sont
négligeables devant g).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Cpmplexité asymptotique

On voit par exemple que O (1) est l’ensemble des fonctions bornées et
que o (1) est l’ensemble des fonctions qui tendent vers 0 pour n → ∞.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Les principales classes de complexité

Dans la pratique on a souvent affaire à des fonctions de complexiteé

dont le comportement asymptotique est un des suivants:
Complexité constante, O (1):
Complexité logarithmique, O (ln n ): Un programme de
complexité logarithmique devient seulement très légèrement plus
lent quand n croît. Chaque fois que n est doublé, le coût
n’augmente que par addition d’une constante. Exemple :
recherche dichotomique.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Les principales classes de complexité

Complexité linéaire O (n ): C’est le mieux que l’on puisse

espérer pour un algorithme qui doit traiter n données une par
une. Chaque fois que n est doublé, le coût double lui aussi.
Exemples : parcourir une liste de longueur n pour trouver le
maximum ou le minimum; addition de deux entiers de longueur
n en numération déimale; déterminer le reste modulo 3 d’un
nombre naturel en numération décimale.
Complexité presque linéaire, O (n ln n ): C’est la complexité
typique pour les algorithmes de type «diviser pour régner ».
Chaque fois que n est doublé, le coût est un peu plus que doublé
(mais guère plus). Exemple : le tri-fusion ou le tri-rapide.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Les principales classes de complexité

Complexité sous-quadratique, O (n α ) avec α < 2: La

multiplication de deux entiers de longueur n en numération
décimale nécessite un temps O (n 1,585 avec la meethode de
Karatsuda. Cette complexité se situe donc entre la complexité
linéaire de l’addition et la complexité quadratique de la
multiplication scolaire.
Complexité quadratique, O (n 2 ): Les complexités quadratiques
sont typiqyes pour les algorithmes traitant tous les couples parli
n données (éventuellement par deux boucles imbriquées).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Complexité Définition et Motivation

Les principales classes de complexité

Complexité polynomiale, O (n k ) avec k > 1: Typiquement un

algorithme qui traite les k-uplets parmi n données est de
complexité O (n k ). De tels algorithmes ne sont utilisables que
pour des problèmes relativement petits. Par exempleL: la
recherche exhaustive des solutions de a 4 + b4 + c 4 = d 4 est de
complexité O (n 4 ).
Complexité exponentielle, O (e αn ) avec α > 0 voire O (e p(n )
avec un polynôme p: Un algorithme de complexité exponentielle
est pratiquement inutilisable, sauf peut-être pour les problèmes
très petits.
Complexité sur-exponentielle: Il existe aussi des fonctions de
croissance sur-exponentielle, comme exp(exp(n )). Des
algorithmes d’une telle complexité n’ont pas d’intérêt pratique; ils
peuvent néanmoins être très importants au niveau théorique,
par exemple pour montrer l’existence d’une solution, aussi
inefficace qu’elle soit.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Calcul de complexité

Pour chaque instruction de base, on peut définir un coût différent:

1 affectation: c1
1 lecture : c2
1 opération arithµétiques: c3
1 test: c4 .
Mais on s’intéresse seulement à la classe de complexité, c’est-à-dire
au coût à une constante multiplicative près.

On approxime donc le coût des instructions par un même et unique c

unitaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Conditionnel

si b alors
algo de complexité C1
sinon
algo de complexité C2
fin si
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Conditionnel

si b alors
algo de complexité C1
sinon
algo de complexité C2
fin si La complexité d’une conditionnelle est:
Si b est vraie, 1 + C1
Si b est fausse, 1 + C2
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Itération "pour"

pour i de a à b faire
algo de complexité Ci
fin pour
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Itération "pour"

pour i de a à b faire
algo de complexité Ci
fin pour

La complexité d’une boucle "pour" est la somme des complexités des

instructions répétées:
b
∑ Ci .
i =a
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Itération "pour"

pour i de a à b faire
algo de complexité Ci
fin pour

En particulier, lorsque qoutes les comoplexité Ci = C pour tout i

pour i de 1 à n faire
algo de complexité C
fin pour
La complexité est de
nC
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Itération conditionnelle: tant que

tant que bi faire

algo de complexité Ci
fin tant que

Le nombre d’itérations dépend souvent des données.

Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Itération conditionnelle: tant que

Différentes notions de complexité (temporelle)

complexité dans dans le pire des cas:
lorsque le nombre d’itération sera maximal
complexité moyenne
nombre d’itérations moyen
complexité dans le meilleur des cas
lorsque le nombre d’itérations sera minimal
La complexité dans le pire des cas est souvent préférée.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Algorithme recherche( x : entier, t: tebleau d’entiers, n: dntier:

booléen
début
variable i: entier
i←0
tant que i < n et t [i ] 6= x faire
i ← i +1
fin tant que
retourner i < n
fin
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Soit t (n ) la complexité pour un tableau de taille n.

c le coût unitaire d’une opération élémentaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Soit t (n ) la complexité pour un tableau de taille n.

c le coût unitaire d’une opération élémentaire.
On a une affectation au début et un test à la fin: cela fait

2c
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Soit t (n ) la complexité pour un tableau de taille n.

c le coût unitaire d’une opération élémentaire.
On a une affectation au début et un test à la fin: cela fait

2c

On a une affectation au début et un test à la fin: cela fait

2c

A chaque itération on a: 2 tests et 1 affectation: cela fait

3c
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

On a une affectation au début et un test à la fin: cela fait

2c

A chaque itération on a: 2 tests et 1 affectation: cela fait

3c

Nombre d’itérations:
Au mieux des cas: 1
Au pire des cas: n
n
en moyenne: .
2
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Ainsi:
La complexité au mieux est: T (n ) = 5c:
T (n ) = Θ(1): complexité constante.
 n
La complexité en moyenne: T (n ) = 2+3 c.
2
T (n ) = Θ(n ): complexité linéaire.
La complexité qu pire: T (n ) = (2 + 3n )c
T (n ) = Θ(n ): complexité linéaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Ainsi:
La complexité au mieux est: T (n ) = 5c:
T (n ) = Θ(1): complexité constante.
 n
La complexité en moyenne: T (n ) = 2+3 c.
2
T (n ) = Θ(n ): complexité linéaire.
La complexité qu pire: T (n ) = (2 + 3n )c
T (n ) = Θ(n ): complexité linéaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple: recherche dans un tableau non ordonné

Ainsi:
La complexité au mieux est: T (n ) = 5c:
T (n ) = Θ(1): complexité constante.
 n
La complexité en moyenne: T (n ) = 2+3 c.
2
T (n ) = Θ(n ): complexité linéaire.
La complexité qu pire: T (n ) = (2 + 3n )c
T (n ) = Θ(n ): complexité linéaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Complexité d’algorithmes récursifs

Le calcul de la complexité d’un algorithme récursif conduit

souvent à l’écriture d’une formmule de récurrence.
Cette récurrence est soit une égalité soit une inégalité.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Complexité d’algorithmes récursifs

Le calcul de la complexité d’un algorithme récursif conduit

souvent à l’écriture d’une formmule de récurrence.
Cette récurrence est soit une égalité soit une inégalité.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple du tri fusion

Problème: Trier un tebleau de données de taille n

Méthode: "diviser pour régner"
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple du tri fusion

En informatique, le tri fusion, ou tri dichotomique, est un algorithme

de tri par comparaison stable. Ce tri est basé sur la technique
algorithmique diviser pour régner. L’opération principale de
l’algorithme est la fusion, qui consiste à réunir deux listes triées en
une seule. L’efficacité de l’algorithme vient du fait que deux listes
triées peuvent être fusionnées en temps linéaire.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple du tri fusion

À partir de deux listes triées, on peut facilement construire une liste

triée comportant les éléments issus de ces deux listes (leur *fusion*).
Le principe de l’algorithme de tri fusion repose sur cette observation :
le plus petit élément de la liste à construire est soit le plus petit
élément de la première liste, soit le plus petit élément de la deuxième
liste. Ainsi, on peut construire la liste élément par élément en
retirant tantôt le premier élément de la première liste, tantôt le
premier élément de la deuxième liste (en fait, le plus petit des deux, à
supposer qu’aucune des deux listes ne soit vide, sinon la réponse est
immédiate).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exemple du tri fusion

Ce procédé est appelé fusion et est au cœur de l’algorithme de tri

développé ci-après.

Algorithme
L’algorithme est naturellement décrit de façon récursive.
1 Si le tableau n’a qu’un élément, il est déjà trié.
2 Sinon, séparer le tableau en deux parties à peu près égales.
3 Trier récursivement les deux parties avec l’algorithme du tri
fusion.
4 Fusionner les deux tableaux triés en un seul tableau trié.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Coût de la fusion

Algorithme fusion(t : tableau, p,q,r : entier)

Entrée:
t est supposé trié entre les indices p et q
t est supposé trié entre les indices q + 1 et r
Sortie
t est trié entre les indices p et r
La complexité de fusionner est en Θ(n ).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Algorithme de tri par fusion

Algorithme triFusion(t : tableau, p, r: entier): rien

début
varible q: entier
si p < r alors
p+r
q←
2
triFusion(t,p,q)
triFusion(t,q+1,r)
fusion(t,p,q,r)
fin si
fin
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Complexité temporelle

T (n ) complexité temporelle pour un tableau de taille n

Diviser: Θ(1), calcul de q
n


Régner: 2T 2
Fusionner: Θ(n ).
On en déduit donc
(
Θ (1) si n = 1
T (n ) = n
+ Θ(n ) si n > 1


2T 2
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Complexité temporelle

Par récurrence, on peut montrer que

n n 
T (n ) ≤ c log
2 2
Soit
T (n ) = O (nlog(n )).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Généralisation

Pour les formule de récurrence de la forme

n 
T (n ) = aT + f (n )
b
avec
a ≥ 1, b ≥ 1 et f asymptotiquement positive.
"Diviser pour régner ": division d’un problème en a
n
sous-problèmes de taille
n  b
T temps d’exécution d’un sous problème
b
f (n ) temps d’exécution de la division et de la fusion.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Généralisation

Théroème (Borne supérieure)

n 
T (n ) = aT + f (n ) avec a ≥ 1 et b ≥ 1 et f asymptotiquement
b
positive.
Posons β = logb (a ). Alors
1 Si ∃α > 0 tel que f (n ) = O ∗ n β−α , alors T (n ) = Θ(n β ).
2 Si f (n ) = Θ(n β ), alors T (n ) = Θ(n β log(n ))
n 
3 Si n β−α = O (f (n )) et ∃c < 1 tel que af ≤ cf (n ) pour n
b
suffisamment grand, alors T (n ) = Θ(f (n )).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Généralisation

Comme application, il faut comparer f (n ) avec n β avec β = logb (a ).

On distingue 3 cas:
Cas 1: f (n ) est plus petit que n β , T (n ) = Θ(n β ).
Cas 2: f (n ) équivalent à n β , T (n ) = Θ(n β log(n )).
Cas 3: f (n ) plus grand que n β et une condition de majoration
sur f , T (n ) = Θ(f (n )).
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exercices

Exercice
La multiplication de deux matrices carrées d’ordre n donne la matrice
carrée C de taille n
 
c11 c12 · · · c1n
 c21 c22 · · · c2n 
C= .
 
.. .. 
 .. . ··· . 
cn1 cn2 · · · cnn
n
avec cij = ∑ aik bkj , ∀i , ∀k.
k =1
1 Ecrire un algorithme qui fait le produit de deux matrices A et B
et stocke le résultat dans C.
2 Déterminer la complexité pour des matrices de taille n.
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exercices

1 Facile
2
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exercices

Exercice
truc() et bidule() sont deux fonctions quelconques sans
argument! Déterminer le nombre de fois qu’elles sont appelées dans
les scripts ci-dessous!

for i in range(n): for i in range(n):

truc() truc()
for j in range(n): for j in range(n):
bidule() bidule()

for i in range(n):
truc()
for j in range(i):
bidule()
Outils mathématiques Evaluation des performances Complexité Définition et Motivation Calcul de complexité

Calcul de complexité

Exercices

for i in range(n):
truc()
for j in range(i):
bidule()
for k in range(j):
bidule()