Algorithmes Récursifs

Algorithmes Récursifs 1 / 29
 Règles de calculs : combinaisons des complexités

Les instructions de base prennent un temps constant, noté O(1) ;

On additionne les complexités d’opérations en séquence :

O(f (n)) + O(g (n)) = O(f (n) + g (n))

Même chose pour les branchements conditionnels :

max(O(f (n)), O(g (n))) = O(f (n)) + O(g (n))

Exemple

si <condition> alors O(g (n)) 
#instructions (1); O(f1 (n))

= O(g (n) + f1 (n) + f2 (n))
sinon 

#instructions (2); O(f2 (n))


Algorithmes Récursifs 2 / 29
 Règles de calculs : combinaison des complexité

Dans les boucles, on multiplie la complexité du corps de la boucle par le nombre

d’itérations ;

Algorithmes Récursifs 3 / 29
 Règles de calculs : combinaison des complexité

Dans les boucles, on multiplie la complexité du corps de la boucle par le nombre

d’itérations ;

Calcul de la complexité d’une boucle while :

Exemple
en supposant qu’on a O(h(n)) itérations
tant que <condition> 
faire O(g (n))
= O(h(n) × (g (n) + f (n)))
#instructions ; O(f (n))

Algorithmes Récursifs 3 / 29
 Règles de calculs : combinaison des complexité

Dans les boucles, on multiplie la complexité du corps de la boucle par le nombre

d’itérations ;

Calcul de la complexité d’une boucle for :

Exemple

pour i allant de a à b faire


#instructions ; = O((b − a + 1) × f (n))
O(f (n))

Algorithmes Récursifs 3 / 29
 Calcul de la complexité asymptotique d’un
algorithme

Pour calculer la complexité d’un algorithme :

1 on calcule la complexité de chaque “partie” de l’algorithme ;

2 on combine ces complexités conformément aux règles qu’on vient de voir ;

3 on simplifie le résultat grâce aux règles de simplifications qu’on a vues ;

F élimination des constantes, et
F conservation du (des) termes dominants

Algorithmes Récursifs 4 / 29
 Exemple : calcul de la factorielle de n ∈ N

Reprenons le calcul de la factorielle, qui nécessitait 3n opérations :

Algorithme : Factorielle(n)
nombre coût
Données : un entier n
Résultat : un entier valant n!
1 fact, i : entier;
2 début
3 fact ← 2; initialisation : Θ(1)× Θ(1)
4 pour i allant de 3 à n faire itérations : Θ(n)× Θ(1)
5 fact ← fact ∗ i; mult. + affect. : Θ(n)× Θ(1)
6 retourner fact; retour fonction : Θ(1)× Θ(1)

Nombre total d’opérations :

Θ(1) + Θ(n) ∗ Θ(1) + Θ(n) ∗ Θ(1) + Θ(1) = Θ(n)

Algorithmes Récursifs 5 / 29
 Exemple : Tri à bulles

La méthode de “comptage” n’est pas toujours applicable directement

Algorithme : TriBulles(T )
nombre coût
Données : un tableau T
Résultat : le tableau T trié
1 début
2 pour i allant de 2 à |T | faire itérations : Θ(|T |)× Θ(1)
3 pour j allant de 1 à i − 1 faire itération : ?× Θ(1)
4 si T [j + 1] < T [j] alors 1ère itération : 1 comparaison
5 échanger(T [j + 1], T [j]); 2ème itération : 2 comparaisons
...

Séries arithmétiques
n
X 1
k = 1 + 2 + 3 + ··· + n = n(n + 1) ∈ Θ(n2 )
2
k=1

Nombre total d’opérations : Θ(|T |2 )

Algorithmes Récursifs 6 / 29
 Récurrences

Algorithme : Fusion(T1,T2)
Stratégie “diviser pour régner” Données : deux tableaux T 1 et T 2
Résultat : un tableau T trié contenant les
éléments de T 1 et de T 2
Algorithme : TriFusion(T ) T : tableau de taille T 1 + T 2;
Données : un tableau T début
Résultat : le tableau T trié si |T 1| = 0 alors
mil : entier; T ← T 2;
début sinon si |T 2| = 0 alors
si |T | ≤ 1 alors T ← T 1;
retourner T ; sinon si T 1[1] < T 2[1] alors
sinon T [1] ← T 1[1];
|T |+1
milieu ← b 2 c; T [2:] ← Fusion(T 1[2:], T 2[1:]);
retourner sinon
Fusion(T [:mil] , T [mil:]); T [1] ← T 2[1];
T [2:] ← Fusion(T 1[1:], T 2[2:]);
retourner T

Algorithmes Récursifs 7 / 29
 Illustration du Tri Fusion

Algorithmes Récursifs 8 / 29
 Récurrences

Temps d’exécution T dans le pire des cas du tri fusion pour trier un tableau de n
entiers

(
Θ(1) si n = 1
T (n) =
2T (n/2) + Θ(n) si n > 1

Complexité du tri fusion : T (n) = Θ(n log n)

Comment passer de l’un à l’autre ?

I Méthode par substitution
I Méthode générale (théorème maître)

Algorithmes Récursifs 9 / 29
 Méthode par substitution

Il faut avoir une intuition sur la forme de la solution (ici : O(n log n))

On veut montrer que T (n) = 2T (bn/2c) + Θ(n) ∈ O(n log n)

On montre par induction qu’il existe f (n) t.q. ∀n T (n) ≤ f (n)

I On va en déduire a posteriori que T (n) ∈ O(f (n))

Attention !
L’hypothèse d’induction est T (n) ≤ f (n), et non T (n) ∈ O(f (n))
L’argument inductif “pour tout x < n, T (x) ∈ O(f (x))” ne veut pas dire grand chose
puisque la notation O est définie pour n arbitrairement grand : on remplace tous les
termes en O, Ω, Θ par une fonction élément de l’ensemble

Algorithmes Récursifs 10 / 29
 Méthode par substitution (condition aux limites)

T (n) = 2T (bn/2c) + n ≤ cn log n

Il faut montrer que la formule est vraie pour les conditions limites de la récurrence
pour des données de petite taille, i.e. n = 1

Problème : c’est faux pour n = 1 car c × 1 × log 1 = 0 < T (1) = 1 ;

Mais on cherche à montrer la complexité pour des données de grande taille : n ≥ n0

et on a le choix pour n0 =⇒ vérifier pour T (2) (et T (3))

On peut aussi borner par f (n) = cn log n + b puisque cn log n + b ∈ O(n log n)
I Ou même f (n) = cn log n + an + b

Algorithmes Récursifs 11 / 29
 Méthode par substitution (condition aux limites)

T (n) = 2T (bn/2c) + n ≤ cn log n

On vérifie que la formule tient pour T (2) et T (3)

T (2) = 2T (b2/2c) + 2

T (2) = 2T (1) + 2

T (2) = 2 ∗ 1 + 2 = 4 ≤ 2c log 2 = 2c

T (2) = 4 ≤ 2c

c≥2
On fait la même chose pour T (3)...
... et on obtient que c doit être ≥ 2.
Algorithmes Récursifs 12 / 29
 Méthode par substitution (Induction)

T (n) = 2T (bn/2c) + n ≤ cn log n

On suppose maintenant que T (x) ≤ cx log x est vrai pour tout 2 ≤ x ≤ n − 1 ; et on

vérifie que c’est aussi le cas pour x = n
T (bn/2c) ≤ cbn/2c logbn/2c

On substitue dans l’expression

T (n) = 2T (bn/2c) + n
≤ 2cb 2n c log(b 2n c) + n
≤ cn log(n/2) + n
= cn log n − cn log 2 + n
= cn log n − cn + n
≤ cn log n

A condition que c ≥ 1 (on prendra c ≥ 2, à cause de T (2) et T (3))

Algorithmes Récursifs 13 / 29
 Méthode générale

Pour les récurrence de la forme T (n) = aT (n/b) + f (n) avec a ≥ 1 et b > 1

L’algorithme découpe la donnée en a sous-problèmes de taille n/b et les résout

récursivement
La fonction f représente le coût de division et de « fusion » du problème.

Exemple pour le tri fusion : a = 2, b = 2 et f (n) = Θ(n)

Exemple pour la recherche binaire : a = 1, b = 2 et f (n) = Θ(1)

Il existe un théorème pour calculer la complexité : le théorème maître

Algorithmes Récursifs 14 / 29
 Théorème maître (général) - version simplifiée

On ne considère que les récurrences T (n) = aT (n/b) + Θ(nd ) (ou O(nd ))

avec a ≥ 1, b > 1, d ≥ 0

1 Si d > logb a, T (n) = Θ(nd ) complexité dominée par le coût de fusion

2 Si d < logb a, T (n) = Θ(nlogb a ) complexité dominée par le coût du sous-problème
3 Si d = logb a, T (n) = Θ(nd log n) pas de domination

Tri fusion : (
Θ(1) si n = 1
T (n) =
2T (n/2) + Θ(n) si n > 1

a = 2, b = 2, d = 1, log2 2 = 1 = d

On est donc dans le cas 3 et la complexité en Θ(n log n)

Algorithmes Récursifs 15 / 29
 Théorème maître (général) - version simplifiée

On ne considère que les récurrences T (n) = aT (n/b) + Θ(nd ) (ou O(nd ))

avec a ≥ 1, b > 1, d ≥ 0

1 Si d > logb a, T (n) = Θ(nd ) complexité dominée par le coût de fusion

2 Si d < logb a, T (n) = Θ(nlogb a ) complexité dominée par le coût du sous-problème
3 Si d = logb a, T (n) = Θ(nd log n) pas de domination

Recherche binaire : (
Θ(1) si n = 1
T (n) =
T (n/2) + Θ(1) si n > 1

a = 1, b = 2, d = 0, log2 1 = 0 = d

On est donc dans le cas 3 et la complexité en Θ(log n)

Algorithmes Récursifs 16 / 29
Taille de la Donnée

Taille de la Donnée 17 / 29
 La taille de la donnée

Taille de la donnée |x|

Espace mémoire nécessaire pour la représenter x
Dans une unité quelconque, fonction de la donnée : |x| ∈ Θ(f (x))

Type primitif entier, flottant, etc. sur 32 ou 64 bits : Θ(1)

Entier non-borné x : |x| ∈ Θ(log x)
Liste L de n caractères : |L| ∈ Θ(n)

Taille de la Donnée 18 / 29
 La taille de la donnée : exemple

La complexité se mesure en fonction de la taille de la donnée

Parfois, on mesure plus facilement la complexité d’un algorithme en fonction d’un
autre paramètre que la taille de la donnée (ex : sa valeur)
Si l’algorithme A est en Θ(f (x)) pour une donnée x et la taille |x| est en Θ(g (x)),
alors la complexité de A sera en Θ(f (g −1 (x)))
Exemple

Algorithme : Carré(x)
Données : un entier x Complexité : Θ(x 2 )
Résultat : un entier valant x 2
r : entier;
début Mais la taille de la donnée est |x| = Θ(log x)
r ← 0;
pour i allant de 1 à x faire
Autrement dit, x = Θ(2|x| )
pour j allant de 1 à x faire
r ← r + 1;
cet algorithme est donc en Θ(22|x| )
retourner r ;
(exponentiel !)

Taille de la Donnée 19 / 29
 La taille d’une structures de données

Dans le cas de structures de données (listes, ensembles, etc.) il faut analyser la

structure : la taille de chaque élément, les pointeurs, etc.

Exemple, liste L de n éléments

Il faut Θ(1) bits
P par élément, plus la somme des tailles des éléments : donc
|L| ∈ Θ(n) + e∈ |e| ⊆ Θ(n) × Θ(|e|)
Les éléments sont des entiers : |L| ∈ Θ(n)
Les éléments sont des entiers non bornés et m est l’élément maximum :
|L| ∈ Θ(n log m)

Taille de la Donnée 20 / 29
 La taille d’une structures de données

La taille des structures va dépendre de leur codage :

Exemple, graphe G = (S, A)

Tableau de tableaux : Il faut Θ(1) bits par arc potentiel, donc
|G | ∈ Θ(|S|2 )
Listes d’adjacence : Il faut Θ(log |S|) bits par arc dans A, donc
|G | ∈ Θ(|A| log |S|)

Taille de la Donnée 21 / 29
 La taille de la donnée

Attention : sujet piégeux !

Taille d’une liste de n entiers (codés sur 32 bits) : Θ(n)
Taille d’une liste de n entiers (où l’élément maximum est m) : Θ(n log m)
Taille d’un ensemble de n entiers (codés sur 32 bits) : Θ(1) ! !
I Il y a un nombre fini d’entiers représentable avec 32 bits (232 ), et donc un nombre fini
32
d’ensembles de tels entiers (22 )

Taille de la Donnée 22 / 29
Classes de Problèmes

Classes de Problèmes 23 / 29
 Vocabulaire

Un algorithme est dit :

en temps constant si sa complexité (dans le pire des cas) est bornée par une constante

linéaire (resp. linéairement borné) si sa complexité (dans le pire des cas) est Θ(n)
(resp. O(n))

quadratique (resp. au plus quadratique) si sa complexité (dans le pire des cas) est
Θ(n2 ) (resp. O(n2 ))

polynômial ou polynômialement borné, si sa complexité (dans le pire des cas) est en

O(np ) pour un certain p > 0

c
(au plus) exponentiel si elle est en O(2n ) pour un certain c > 0

Classes de Problèmes 24 / 29
 Classes de problèmes

Analyser la complexité des algorithmes permet de faire un choix éclairé, mais pas
seulement

Classer les problèmes

I en fonction de la complexité du meilleur algorithme connu pour les résoudre

TIME (f (n))
Ensemble des problèmes pour lesquels il existe un algorithme en O(f (n))

Tri ∈ TIME(n log n)

Recherche dans un tableau trié ∈ TIME(log n)
Tout algorithme de tri est en Ω(n log n) =⇒ Tri 6∈ TIME(n)
Trier est plus “difficile” que chercher dans un tableau trié

Classes de Problèmes 25 / 29
 Classes de problèmes (suite)

On peut analyser l’espace mémoire utilisé par un algorithme de manière similaire

SPACE (f (n))
Ensemble des problèmes pour lesquels il existe un algorithme nécessitant
O(f (n)) octets

On ne compte pas la taille de la donnée, mais on compte la taille de la réponse

Théorème
TIME(f (n)) ⊆ SPACE(f (n))

Problème A ∈ TIME(f (n)) =⇒ A ∈ SPACE(f (n))

Chaque octet utilisé implique Ω(1) opération(s)

Classes de Problèmes 26 / 29
 Parcours de Graham

Trouver l’enveloppe convexe d’un 2

ensemble de points
6
8

Algorithme
4
1 Trouver le point p de plus petite
ordonnée O(n)
5
2 Trier les autres points en fonction de 9
l’angle avec l’axe des abcisses par
rapport à p 7
1
3 Appliquer le parcours de Graham O(n)
10
I retour arrière en cas de “tournant à
droite”

Classes de Problèmes 28 / 29
 Réduction polynômiale

On peut trouver l’enveloppe convexe en O(n) plus le coût de trier n entiers

Tri ∈ TIME(n log n) =⇒ Enveloppe convexe ∈ TIME(n log n)

Réduction de Enveloppe convexe vers Tri :

I Enveloppe convexe pas plus difficile que Tri
I Tri au moins aussi difficile que Enveloppe convexe

Réduction polynômiale de A vers B (de Cook / de Turing) :

Un algorithme pour résoudre A en O(nc ) (pour c un constante et n la taille
de la donnée) sous l’hypothèse que le problème B peut être résolu en Θ(1)

Classes de Problèmes 29 / 29