Notes du cours : Algorithmique et complexité

Niveau: MR1 GL de Mme Manel SEKMA

ISIM Monastir
A.U: 2024-2025

Complexité et Algorithme

Niveau: MR1 GL
Notes du cours de [Link] SEKMA
[Link]@[Link]

2024/2025
 Chapitre 2 :
RÉCURSIVITÉ ET PARADIGME DIVISER POUR
RÉGNER

Objectif: La récursivité
Plan de chapitre 2:
 Introduction
 La récursivité
 La dérécursivation
 Le paradigme « Diviser pour régner »
2 Notes du cours : Algorithmique et complexité
SEKMA.M
La récursivité

 Définitions

 Evolution d’un appel récursif

 Types de la récursivité

 Récursivité terminale vs non terminale

 Complexité des algorithmes récursifs

 Ecrire un algorithme récursif

 Exemple:Tours de Hanoi

3 Notes du cours : Algorithmique et complexité

SEKMA.M
Pourquoi étudier la complexité des
algorithmes récursifs ?

 Leur comportement en termes de temps et d'espace

n'est pas toujours évident à première vue, car chaque
appel récursif peut entraîner plusieurs autres appels.

4 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Définitions
 Un algorithme est dit récursif s’il est défini en fonction de lui-
même
 Exemple: la factorielle n!

Itératif Récursif
n!= 1  2 …..  n n!= n  ( n-1)!
Facto (n: entier): entier Facto (n: entier): entier
Début Début
F1; Retourne n  Facto (n-1);
Pour i2 à n faire Fin
FF  i;
Retourne F;
Fin

5 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Evolution d’un appel récursif
 L’exécution d’un appel récursif passe par deux phases, la phase de
descente et la phase de la remontée.
 Dans la phase de descente, chaque appel récursif fait à son tour un appel
récursif.
Facto (n: entier): entier
 Exemple: 4!=Facto (4) Début
Retourne n  Facto (n-1);
Fin
Facto (4)4  Facto (3)
Facto (3)3  Facto (2)
Facto (2)2  Facto (1)
Facto (1)1  Facto (0)
Facto (0)0  Facto (-1)

6 Notes du cours : Algorithmique

Complexité Algorithmique
et complexité
SEKMA.M
La récursivité
 Evolution d’un appel récursif
 Condition d’arrêt?
 Puisqu’un algorithme récursif s’appelle lui-même, il est impératif qu’on
prévoit une condition d’arrêt à la récursion, sinon le programme ne
s’arrête jamais!
 Même exemple: la factorielle n!

Condition d’arrêt?

Facto (n: entier): entier Facto (n: entier): entier

Début Début
Retourne n  Facto (n-1); Si (n=1) alors retourne 1
Fin Sinon retourne n  Facto (n-1);
Fin

7 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Evolution d’un appel récursif
 En arrivant à la condition terminale, on commence la phase de la
remontée qui se poursuit jusqu’à ce que l’appel initiale doit terminé, ce
qui termine le processus récursif.

Facto (n: entier): entier

Début
Si (n=1) alors retourne 1
Sinon retourne n  Facto (n-1);
24
Fin
Facto (4)4  Facto (3)

Phase de la remontée
6
Facto (3)3  Facto (2) 1
2
Facto (2)2  Facto (1)
8 Notes du cours : Algorithmique et complexité
SEKMA.M
La récursivité
 Type de récursivité
1) La récursivité simple: où l’algorithme contient un seul appel récursif dans
son corps. Facto (n: entier): entier
 Exemple : la fonction factorielle Début
Si (n=1) alors retourne 1
Sinon retourne n  Facto (n-1);
Fin
2) La récursivité multiple: où l’algorithme contient plus d’un appel récursif
dans son corps.
 Exemple : le calcul du nombre de combinaisons en se servant de la relation de
Pascal:

Fonction combinaisons (n: entier, p: entier): entier

Si (p=1 OU p=n) alors retourne 1;
Fin si
retourne combinaisons (n-1, p)+ combinaisons (n-1, p-1);
Fin

9 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Type de récursivité
3) La récursivité mutuelle: des modules sont dits mutuellement récursifs s’ils
dépendent les uns des autres.
 Exemple : la définition de la parité d’un entier peut être écrite de la manière
suivante:
=0 =0
Pair(n) = Impair(n) =
−1 −1

Fonction Pair (n: entier): Boolean Fonction Impair (n: entier): Boolean
Si (n=0) alors retourne vrai; Si (n=0) alors retourne faux;
Fin si Fin si
retourne Impair(n-1); retourne pair(n-1);
Fin Fin

10 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Type de récursivité
4) La récursivité imbriquée: consiste à faire un appel récursif à l’interieur
d’un autre appel récursif.
 Exemple : la fonction d’Ackermann
+1 =0
A(m,n)= − 1, 1 >0 =0
− 1, , −1

Fonction Ackerman (n: entier, m: entier): entier

Si (m=0) alors retourne n+1;
Fin si
Si (n=0 ET m>0) Alors
retourne Ackerman(m-1, 1);
Sinon
retourner Ackerman(m-1, Ackerman(m, n-1));
Fin si

Fin

11 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Récursivité terminale vs non terminale
 Un module récursif est dit terminal si aucun traitement n’est effectué à
la remontée d’un appel récursif (sauf le retour du module).

 Un module récursif est dit non terminal si le résultat de l’appel récursif

est utilisé pour réaliser un traitement (en plus du retour du module)

Récursivité non terminale Récursivité Terminal

Facto (n: entier): entier Facto (n: entier, résultat: entier): entier
Début Début
Si (n=1) alors retourne 1 Si (n=1) alors retourne résultat;
Sinon retourne n  Facto (n-1); Sinon retourne Facto (n-1, n résultat );
Fin Fin

12 Notes du cours : Algorithmique et complexité

SEKMA.M
 La récursivité
Récursivité non terminale

Facto (n: entier): entier

Début
Si (n=1) alors retourne 1
Sinon retourne n  Facto (n-1);
Fin

 le dernier return est en fait l'appel récursif et

nous soustrayons 1 à chaque appel jusqu'à ce
que n == 1 qui est la condition de sortie.

 Lorsque la fonction rencontre la condition de sortie, elle remonte dans tous les appels
précédents pour calculer n avec la valeur précédemment trouvée .
 Les appels des fonctions récursives sont en fait empilés

13 Notes du cours : Algorithmique et complexité

SEKMA.M
 La récursivité
Récursivité non terminale

Si nous devrions calculer le factoriel de 49 ce qui nous donne: 49! = 49x48x47 … 8x7x6! ;

le résultat obtenu est d'une grandeur inimaginable ! ……comment faire avec la pile!!

exploser la pile ce qui conduirait irrémédiablement au plantage du programme !

Facto (n: entier): entier

Début
Si (n=1) alors retourne 1
Sinon retourne n  Facto (n-1);
Fin
Récursivité non terminale

14 Notes du cours : Algorithmique et complexité

SEKMA.M
 La récursivité
Récursivité terminale

 les appels de la fonction n'ont pas besoin d'être empilés, car

l'appel suivant remplace simplement l'appel précédent dans
le contexte d'exécution

Facto (n: entier, résultat: entier): entier

Début
Si (n=1) alors retourne résultat;
Sinon retourne Facto (n-1, n résultat );
Fin

15 Notes du cours : Algorithmique et complexité

SEKMA.M
Complexité des algorithmes récursifs
1. Identifiez la récurrence : Comprenez comment l'algorithme divise le

problème en sous-problèmes.

2. Écrivez la relation de récurrence : Exprimez la complexité en fonction de

la taille de l'entrée (p. ex. T(n)).

3. Identifiez les cas de base : Déterminez les cas simples où la récusions

s'arrêtent.

4. Évaluez la complexité des appels récursifs : Déterminez le coût de

chaque appel récursif en fonction de la taille de l'entrée.

16 Notes du cours : Algorithmique et complexité
SEKMA.M
Complexité des algorithmes récursifs
5. Écrivez la relation de récurrence complète : Formulez une équation qui

décrit la complexité en fonction de n.

6. Résolvez la récurrence : Utilisez des méthodes de résolution de récurrences

pour déterminer la complexité.

7.Vérifiez la solution : Assurez-vous que la solution correspond à la réalité et

aux cas de base.

8. Analyse asymptotique : Exprimez la complexité en notation "grand O" pour

évaluer la croissance en fonction de la taille de l'entrée.

17 Notes du cours : Algorithmique et complexité

SEKMA.M
 Exemple Complexité des algorithmes
récursifs
Exemple: la fonction factorielle, soit T(n) est le temps d’exécution
nécessaire pour un appel à facto(n)

Facto (n: entier): entier

Début
Si (n=1) O(1) alors
a =1
T(n) =
retourne 1 O(1) + −1
Sinon
b retourne n  Facto (n-1); T(n) dépend de T(n-1)
Fin

18 Notes du cours : Algorithmique et complexité

SEKMA.M
Exemple Complexité des algorithmes
récursifs
 Écrivez la relation de récurrence :
 T(n) = b + T(n - 1)
 Supposez une solution :
 Supposer que T(n) = a*n + c est la solution.
Ici, a et c sont des constantes qu’on doit déterminer.
 Appliquez la solution supposée :
 Remplacez T(n) par a*n + c dans la relation de récurrence :
a*n + c = b + a*(n - 1) + c.
 Simplifiez l'équation :
 Réorganisez l'équation pour résoudre a et c. Dans ce cas, on
remarque que a est égal à b et c est égal à b.
 Exprimez la solution finale :
 La solution de la récurrence est T(n) = b*n + b

19 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Complexité des algorithmes récursifs
 Pour calculer la solution générale de cette équation, par substitution:
T(n)= b+ T(n-1)
= b+[b+ T(n-2)]
= 2b+ T(n-2)
= 2b+[b+ T(n-3)]
= ……
= ib+T(n-i)
= ib+[b+ T(n-i+1)]
= ……
= (n-1)b+T(n-n+1)= nb-b+T(1) = nb – b + a
T(n)= nb – b + a O(T)= O(n)
20 Notes du cours : Algorithmique et complexité
SEKMA.M
La récursivité
 Complexité des algorithmes récursifs
 Dans un module récursif (procédure ou fonction) les paramètres
doivent être clairement spécifiés.

 Dans le corps du module il doit y avoir :

 Un ou plusieurs cas particuliers: ce sont les cas simples qui ne nécessitent pas
d’appels récursifs.

 Un ou plusieurs cas généraux: ce sont les cas complexes qui sont résolus par des
appels récursifs.

 L’appel récursif d’un cas général doit toujours mener vers un des cas
particuliers.

21 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
 Déplacer n disques (empilés les uns sur les autres) d’un piquet (A) vers
un autre piquet (B) en utilisant un troisième (C) comme intermédiaire.
 Ce sont des piles alors on ne peut accéder qu’au disque du sommet.
 Un disque ne peut jamais être placé au dessus d’un autre plus petit.

22 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
 Conception de la solution récursive
 Il faut pouvoir exprimer:

 Le déplacement de n disques en fonction d’un ou de plusieurs

déplacement de m disques ( avec m<n)

 Par exemple ( m=n-1) si on avait une solution pour déplacer n-1 disques,
comment l’utiliser pour déplacer n disques?

23 Notes du cours : Algorithmique et complexité

SEKMA.M
 Exemples des Tours de Hanoi
Conception de la solution récursive

24 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
Algorithme informel
Pour transformer n disques de A vers B avec C comme
intermédiaire, il faut:
 Cas particulier (n=1)
 Déplacer le disque de X vers Y
 Cas général ( n>1)
 Transférer les n-1 premiers disques de A vers C, en utilisant B comme
intermédiaire.
 Déplacer l’unique disque qui reste de A vers B
 Transférer les n-1 premiers disques de C vers B, en utilisant A comme
intermédiaire.

25 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
Algorithme Final
Hanoi( n:entier; A, B, C: caractères)
Si (n=1)
Ecrire(« Déplacer un disque de A vers B);
Sinon
Hanoi (n-1, A, C, B);
Ecrire (« Déplacer un disque de A vers B);
Hanoi ( n-1, C,A, B);
Fin Si

26 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
Autre version
Hanoi( n:entier; A, B, C: caractères)
Si (n>0)
Hanoi (n-1, A, C, B);

Ecrire (« Déplacer un disque de A vers B);

Hanoi ( n-1, C, B, A);

Finsi

27 Notes du cours : Algorithmique et complexité

SEKMA.M
La récursivité
 Exemples des Tours de Hanoi
Complexité
Hanoi( n:entier; A, B, C: caractères) T(n), O(T)= ?

Si (n>0)
Hanoi (n-1, A, C, B); T(n-1)
Ecrire (« Déplacer un disque de A vers B); O(1)

Hanoi ( n-1, C, B, A); T(n-1)

Fin Si

T(n)=2T(n-1)+a=2(2T(n-2)+a=22T(n-2)+2a+a
=........
=2 T(0) + (2 + 2 +2 +. . . . . . . . .+2 )a O(T)=
= 2 0 + (2 - 1) a

28 Notes du cours : Algorithmique et complexité

SEKMA.M
Plan de chapitre 2:
 Introduction
 La récursivité
 La « dérécursivation »
 Le paradigme « Diviser pour régner »

29 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation

 Généralités

 Elimination de la récursivité terminale simple

 Elimination de la récursivité terminale multiple

 Elimination de la récursivité non terminale simple

 Elimination de la récursivité: Algorithme Général

30 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation
 Généralités
 Au niveau de l’utilisateur: la récursivité permet d’écrire des
algorithmes concis et élégants.

 Au niveau de la machine: le compilateur élimine toujours la

récursivité ( "Dérécursiver") en construisant un programme itératif
(ensemble des instructions séquentielles) afin d’économiser l’espace
de la pile d’exécution.

 "Dérécursiver", c’est transformer un algorithme récursif en un

algorithme itératif équivalent ne contenant pas de appels récursifs.

31 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation
 Elimination de la récursivité Terminale Simple
 Rappel: un algorithme est dit récursif terminal s’il ne contient aucun
traitement après un appel récursif.

Procédure ALGO (X) // Liste des paramètres

Si (condition) alors // condition portant sur X

<Traitement 1> // traitement de base de l’algorithme (dépendant de X)

ALGO (B(X)) // B(X) représente la transformation des paramètres

// Rien

Sinon
<Traitement 2> // Traitement de terminaison (dépendant de X)

Finsi

32 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation
 Elimination de la récursivité Terminale Simple
Algorithme Récursif Algorithme Itératif

Procédure ALGO-Rec (X) Procédure ALGO-Iter(X)

Début Début
Si (condition) alors Tant que (condition) faire
<Traitement 1> <Traitement 1>

ALGO-Rec (B(X)) XB(X)

Sinon FTQ
<Traitement 2> <Traitement 2>

Finsi Fin
Fin
33 Notes du cours : Algorithmique et complexité
SEKMA.M
La dérécursivation
Elimination de la récursivité Terminale Simple
Exemple: 1 Factorielle

Algorithme Récursif Algorithme Itératif

Procédure Facto-Rec (n, resultat) Procédure Facto-Iter (n, resultat)

Début Début
Si (n>1) alors resultat1
Retourner (Facto-Rec (n-1, n resultat)) Tant que (n>1) faire
Sinon resultatn  resultat
Retourner (resultat) nn-1
Finsi FTQ
Fin Retourner (resultat)
Fin
34 Notes du cours : Algorithmique et complexité
SEKMA.M
La dérécursivation
Elimination de la récursivité Terminale Simple
Exemple: PGCD
Ecrire une fonction récursive permettant de calculer le PGCD (Plus Grand Commun
Diviseur ) de deux nombres naturels non nul (a, b) en utilisant l’algorithme d’Euclide:

=
PGCD (a,b) − , >
, − <

35 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation
Elimination de la récursivité Terminale Simple
Exemple: PGCD
Algorithme Récursif Algorithme Itératif
Procédure PGCD-Rec (a, b) Procédure PGCD-Iter (a, b)
Début Début
Si (a=b) alors Tant que (ab) faire
Retourner (a)
Si (a>b) alors aa-b
Sinon
Sinon bb-a
Si (a>b) alors
FTQ
Retourner (PGCD-Rec (a-b, b))
Retourner (a)
Sinon
Fin
Retourner (PGCD-Rec (a, b-a))
Finsi
Fin36 Notes du cours : Algorithmique et complexité
SEKMA.M
La dérécursivation
Elimination de la récursivité Terminale Simple
 Dans un algorithme récursif non terminal, l’appel récursif est suivi d’un traitement
 Il reste un traitement (Traitement 2) à reprendre après l’appel récursif.

Procédure ALGO (X) // Liste des paramètres

Si (condition) alors // condition portant sur X

<Traitement 1> // traitement de base de l’algorithme (dépendant de X)

ALGO (B(X)) // B(X) représente la transformation des paramètres

<Traitement 2>
Sinon
<Traitement 3> // Traitement de terminaison (dépendant de X)

Finsi

37 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation
Elimination de la récursivité Terminale Simple
 Il faut donc sauvegarder le contexte de l’appel récursif
(typiquement les paramètres de l’appel engendrant l’appel
récursif) sur une pile.

 Les piles sont des structures de stockage qui fonctionnent sur

le principe LIFO " Last In First Out ": le dernier entré est le
premier sorti »

 Le principe est de simuler la pile d’appels des processus pour

éliminer la récursivité non terminale.

38 Notes du cours : Algorithmique et complexité

SEKMA.M
Elimination de la récursivité
Algorithme général
1. Définir la zone de données
 Contient les paramètres, l’adresse du retour et les variables locales

2. Définir les points d’appel et de retour.

 Il y a donc toujours un appel dans l’algorithme appelant. C’est le premier appel.

3. Appel de la procédure
3.1. Empiler la zone de données courante
3.2. Préparer le nouvel appel en préparant la nouvelle zone de données avec les paramètres (passage
de paramètres) et avec l’adresse de retour (point d’appel).
3.3. Se brancher vers le début de la fonction

4. Retour de la procédure
4.1. Récupérer l’adresse de retour qui se trouve dans la zone de données courante.
4.2. Dépiler une zone de donnée (restaurer la dernière sauvegardée)
4.3. Se brancher vers cette adresse.

39 Notes du cours : Algorithmique et complexité

SEKMA.M
La dérécursivation….conclusion
 Les programmes itératifs sont souvent plus efficaces, mais les programmes

récursifs sont plus faciles à écrire.

 Les compilateurs savent, la plupart du temps reconnaitre les appels

récursifs terminaux, et ceux-ci n’engendrent pas de surcoût par rapport à

la version itérative du même programme.

 Il est toujours possible de « dérécursiver » un algorithme récursif.

40 Notes du cours : Algorithmique et complexité

SEKMA.M
Plan de chapitre 2:
 Introduction
 La récursivité
 La « dérécursivation »
 Le paradigme « Diviser pour régner »

41 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »

 Principe

 Complexité des algorithmes « Diviser pour

Régner »

 Méthodes de résolution des récurrences

42 Notes du cours : Algorithmique et complexité

SEKMA.M
 Le paradigme « Diviser pour régner »

 Principe

 La récursivité est un outils permet de concevoir des solutions

simples sans se préoccuper des détails algorithmiques interne.

 Le paradigme « Diviser pour régner » permet de spécifier la

solution du problème en fonction de la ou des solutions (s) d’un (

ou de plusieurs) sous-problèmes plus simple(s)

43
Notes du cours : Algorithmique et complexité
SEKMA.M
 Le paradigme « Diviser pour régner »

 Comment trouver la solution d’un sous-problème??

 Ce n’est pas important car on prendra comme hypothèse que

chaque appel récursif résoudra un sous-problème.

 Si on arrive à trouver une solution globale en utilisant ces

hypothèses, alors ces dernières (les hypothèses) sont forcément
correctes, de même que la solution globale

 Cela ressemble à la « démonstration par récurrence ».

44 Notes du cours : Algorithmique et complexité
SEKMA.M
Le paradigme « Diviser pour régner »
 Principe

45 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
 Exemple 1: Recherche le Maximum
 Soit T un tableau à n éléments, écrire une fonction récursive permettant de
rechercher l’indice du maximum dans T en utilisant le paradigme diviser
pour régner!

46 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
 Exemple: Recherche le Maximum

47 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
 Exemple 2: Recherche Dichotomique
 Soit T un tableau trié à n éléments,

 La recherche par dichotomie compare l’élément cherché X avec

l’élément en position m situé au milieu de sous-tableau.
 Si T[m] = X : on a trouvé l’élément en position m
 Si T[m] > X : il est impossible que X se trouve après la position m dans le tableau
T. Il reste à traiter uniquement la moitié inférieure du tableau.
 De même si Tab[m] < X : il reste à traiter uniquement la moitié supérieure du
tableau.

 On continue ainsi la recherche jusqu’à trouver l’élément ou bien aboutir

sur un tableau de taille nulle, X n’est pas présent et la recherche
s’arrête.

48 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
 Exemple 2: Recherche Dichotomique

49 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
 Méthodes de résolution des récurrences
 Boucles itératives, fonctions récursives (approches de type
diviser pour régner notamment)
 Pour résoudre une récurrence on va étudié quelques
méthodes, à savoir:
 La méthode par substitution
 La méthode par développement itératif
 La méthode générale (Master theorem) appliquée seulement sur les
récurrences « diviser pour régner »

50 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
 Exemple : Tri par fusion
 Soit S un tableau à n éléments,

51 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences

La méthode par substitution

Cette méthode recouvre Trois phases:

 Conjecturer (imaginer) la forme de la solution

 Employer une récurrence mathématique pour trouver les constantes et

prouver que la solution est correcte par induction.

 Vérifier pour les cas de base.

52 Notes du cours : Algorithmique et complexité

SEKMA.M
 Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
1. La méthode par substitution

Exemple : Tri par fusion

53 Notes du cours : Algorithmique et complexité

SEKMA.M
 Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
2. La méthode par développement itératif
Exemple : Tri par fusion

54 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
3. La méthode générale (Master theorem)

 DIVISER le problème en a sous-pbs de taille n/b

 RESOUDRE les sous-problèmes récursivement
 FUSIONNER les réponses aux sous-pbs en O( ) afin d'obtenir la réponse au
problème de départ

A partir de la connaissance des valeurs des paramètres a, b et k, le théorème

maître permet de déterminer « automatiquement » la complexité d'une
méthode de type diviser pour régner.

55 Notes du cours : Algorithmique et complexité

SEKMA.M
 Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
3. La méthode générale (Master theorem)
 Le temps d’exécution d’un algorithme « diviser pour régner » se décompose
suivant les trois étapes du paradigme de base.

 Diviser le problème en a sous-problèmes chacun de taille 1/b de la taille du

problème initial. Soit D(n) le temps nécessaire à la division du problème en sous-
problèmes.

 Combiner: soit C(n) le temps nécessaire pour construire la solution finale à partir
des solutions aux sous-problèmes.

T(n)=a T(n/b)+ D(n) + C(n)

Soit la fonction f(n) la fonction qui regroupe D(n) et C(n) alors la fonction T(n) est:

T(n)=a T(n/b)+ f(n)

56 Notes du cours : Algorithmique et complexité
SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
3. La méthode générale (Master theorem)

57 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
3. La méthode générale (Master theorem)

 Si on peut montrer que f(n)=g(n)  ( ) pour un certain k, alors le

théorème suivant nous donne automatiquement la complexité de l’algorithme:

 Pour f(n)= c , on a : T(n)=a T(n/b)+ c avec a>0, b>1 et k≥0

58 Notes du cours : Algorithmique et complexité

SEKMA.M
Le paradigme « Diviser pour régner »
Méthodes de résolution des récurrences
 Exemples:
 Complexité de l’algorithme de recherche du maximum:
T(n)= 2 T(n/2) + c
a=2, b=2, k=0 alors a > avec log a=1
T(n) = O(n)
 Complexité de l’algorithme de recherche dichotomique:
T(n)=T(n/2) + c
a=1, b=2, k=0 alors a =
T(n) = O(log(n))

59 Notes du cours : Algorithmique et complexité

SEKMA.M
Exemples
montrer que :
1. T(n)= 9 T(n/3) + n = O(n²) ?
2. T(n)= 3 T(n/4) + n log n = O(n log n)?

60 Notes du cours : Algorithmique et complexité

SEKMA.M