Récurrences
Prof Gervais Mendy
[Link]@[Link]
December 13, 2021
Plan
Introduction à la Récurrence
La méthode de substitution
La méthode de l’arbre récursif
La méthode générale
Trois cas usuels
Application de la méthode générale
2 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
L’analyse des performances d’un algorithme donne en générale
des équations implicites
3 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
L’analyse des performances d’un algorithme donne en générale
des équations implicites
Ainsi le temps de calcul, pour une taille des données, est
exprimé en fonction du temps de calcul pour des données plus
petites.
3 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
Hypothèse: algorithme contenant un appel récursif à lui-même.
Son temps d’exécution peut souvent être décrit par une
récurrence.
4 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
Hypothèse: algorithme contenant un appel récursif à lui-même.
Son temps d’exécution peut souvent être décrit par une
récurrence.
Une récurrence est une équation ou inégalité qui décrit une
fonction à partir de sa valeur sur des entrées plus petites
4 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
Résolution des récurrences: Nous présentons trois méthodes
pour résoudre les récurrences, c’est-à-dire pour obtenir des bornes
asymptotiques Θ ou O pour la solution.
méthode de substitution
5 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
Résolution des récurrences: Nous présentons trois méthodes
pour résoudre les récurrences, c’est-à-dire pour obtenir des bornes
asymptotiques Θ ou O pour la solution.
méthode de substitution
méthode de l’arbre récursif
5 on 34
Introduction à la Récurrence
Introduction à la Récurrence
Notion de Récurrence
Résolution des récurrences: Nous présentons trois méthodes
pour résoudre les récurrences, c’est-à-dire pour obtenir des bornes
asymptotiques Θ ou O pour la solution.
méthode de substitution
méthode de l’arbre récursif
méthode générale
5 on 34
La méthode de substitution
Description de la méthode
Étapes de la méthode de substitution
Approche: Dans la méthode de substitution, on devine une borne
puis on utilise une récurrence mathématique pour démontrer la
validité de la conjecture.
Conjecturer la forme de la solution.
6 on 34
La méthode de substitution
Description de la méthode
Étapes de la méthode de substitution
Approche: Dans la méthode de substitution, on devine une borne
puis on utilise une récurrence mathématique pour démontrer la
validité de la conjecture.
Conjecturer la forme de la solution.
Employer une récurrence mathématique pour trouver les
constantes et prouver que la solution est correcte.
6 on 34
La méthode de substitution
Description de la méthode
Commentaire sur la méthode de substitution
méthode puissante
7 on 34
La méthode de substitution
Description de la méthode
Commentaire sur la méthode de substitution
méthode puissante
forme de la réponse pas facile à deviner
7 on 34
La méthode de substitution
Description de la méthode
Exemple de résolution
T (n) = 2T (bn/2c) + n, (1)
8 on 34
La méthode de substitution
Description de la méthode
Exemple de résolution
T (n) = 2T (bn/2c) + n, (1)
Conjecture : la solution est T (n) = O(n log n).
récurrence : on suppose que cette borne est valable pour
bn/2c
autrement dit que
T (bn/2c) = O(bn/2c log(bn/2c)).
8 on 34
La méthode de substitution
Exemple de substitution
Preuve de la conjecture: Récurrence
On prouve qu’il existe une constante c > 0 telle que T (bn/2c) ≤
cbn/2c log(bn/2c). La substitution donne
T (n) ≤ 2(cbn/2c log(bn/2c)) + n
≤ cn log(n/2) + n
= cn log n − cn log 2 + n
= cn log n − cn + n
≤ cn log n
la dernière étape étant vraie si c ≥ 1
9 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Illustration du problème:
Pour la récurrence (1), Supposons que T (1) = 1 soit l’unique
condition aux limites.
10 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Illustration du problème:
Pour la récurrence (1), Supposons que T (1) = 1 soit l’unique
condition aux limites.
Alors, pour n = 1, la borne T (n) ≤ cn log n donne
T (1) ≤ c1 log 1 = 0
10 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Illustration du problème:
Pour la récurrence (1), Supposons que T (1) = 1 soit l’unique
condition aux limites.
Alors, pour n = 1, la borne T (n) ≤ cn log n donne
T (1) ≤ c1 log 1 = 0
Contradiction de la condition aux limites T (1) = 1
10 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Illustration du problème:
Pour la récurrence (1), Supposons que T (1) = 1 soit l’unique
condition aux limites.
Alors, pour n = 1, la borne T (n) ≤ cn log n donne
T (1) ≤ c1 log 1 = 0
Contradiction de la condition aux limites T (1) = 1
Donc cas initial de la démonstration inductive pas vérifié.
10 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Notation asymptotique: pour contourner la difficulté.
On doit démontrer que T (n) ≤ cn log n pour n ≥ n0 ,
11 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Notation asymptotique: pour contourner la difficulté.
On doit démontrer que T (n) ≤ cn log n pour n ≥ n0 ,
où n0 est une constante de notre choix.
11 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Notation asymptotique: pour contourner la difficulté.
On doit démontrer que T (n) ≤ cn log n pour n ≥ n0 ,
où n0 est une constante de notre choix.
Notons que, pour n > 3, la récurrence ne dépend pas
directement de T (1).
11 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Notation asymptotique: pour contourner la difficulté.
On doit démontrer que T (n) ≤ cn log n pour n ≥ n0 ,
où n0 est une constante de notre choix.
Notons que, pour n > 3, la récurrence ne dépend pas
directement de T (1).
On peut donc remplacer T (1) par T (2) et T (3) comme cas
initiaux de la démonstration par récurrence, en faisant n0 = 2.
11 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Remarque:
Une distinction faite entre le cas initial de la récurrence (n = 1)
et les cas initiaux de la démonstration (n = 2 et n = 3).
12 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Remarque:
Une distinction faite entre le cas initial de la récurrence (n = 1)
et les cas initiaux de la démonstration (n = 2 et n = 3).
Nous déduisons de la récurrence que T (2) = 4 et T (3) = 5.
12 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Remarque:
Une distinction faite entre le cas initial de la récurrence (n = 1)
et les cas initiaux de la démonstration (n = 2 et n = 3).
Nous déduisons de la récurrence que T (2) = 4 et T (3) = 5.
Compléter la démonstration par récurrence que T (n) ≤ cn log n
pour une certaine constante c ≥ 1.
12 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Remarque:
Une distinction faite entre le cas initial de la récurrence (n = 1)
et les cas initiaux de la démonstration (n = 2 et n = 3).
Nous déduisons de la récurrence que T (2) = 4 et T (3) = 5.
Compléter la démonstration par récurrence que T (n) ≤ cn log n
pour une certaine constante c ≥ 1.
Choisir c suffisamment grand pour que T (2) ≤ c2 log 2 et
T (3) ≤ c3 log 3.
12 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Remarque:
Une distinction faite entre le cas initial de la récurrence (n = 1)
et les cas initiaux de la démonstration (n = 2 et n = 3).
Nous déduisons de la récurrence que T (2) = 4 et T (3) = 5.
Compléter la démonstration par récurrence que T (n) ≤ cn log n
pour une certaine constante c ≥ 1.
Choisir c suffisamment grand pour que T (2) ≤ c2 log 2 et
T (3) ≤ c3 log 3.
c ≥ 2 valide les cas initiaux de n = 2 et n = 3.
12 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Synthèse:
L’induction mathématique exige que nous montrions que notre
solution est valable pour les conditions aux limites.
13 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Synthèse:
L’induction mathématique exige que nous montrions que notre
solution est valable pour les conditions aux limites.
En général, on le fait en montrant que les conditions aux limites
peuvent servir de cas initiaux pour la démonstration par
récurrence.
13 on 34
La méthode de substitution
Méthode de substitution
Gestion des conditions aux limites
Synthèse:
L’induction mathématique exige que nous montrions que notre
solution est valable pour les conditions aux limites.
En général, on le fait en montrant que les conditions aux limites
peuvent servir de cas initiaux pour la démonstration par
récurrence.
Pour la plupart des récurrences que nous étudierons, il sera
immédiat d’étendre les conditions aux limites de façon que
l’hypothèse de récurrence soit vraie pour n petit.
13 on 34
La méthode de substitution
Méthode de substitution
Synthèse générale
1. Conjecturer de la forme de la solution
2. Vérifier par induction
3. Résoudre pour les constantes (conditions aux limites)
14 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Approche
Tracer un arbre récursif
15 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Approche
Tracer un arbre récursif
Déduire une bonne conjecture
15 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Description
Chaque nœud représente le coût d’un sous-problème
individuel
16 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Description
Chaque nœud représente le coût d’un sous-problème
individuel
On totalise les coûts pour chaque niveau de l’arbre
16 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Description
Chaque nœud représente le coût d’un sous-problème
individuel
On totalise les coûts pour chaque niveau de l’arbre
On cumule tous les coûts par niveau pour calculer le coût total
de la récursivité
16 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Description
Chaque nœud représente le coût d’un sous-problème
individuel
On totalise les coûts pour chaque niveau de l’arbre
On cumule tous les coûts par niveau pour calculer le coût total
de la récursivité
Générer une bonne conjecture, confirmée ensuite via la
méthode de substitution.
16 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Exemple d’utilisation
Soit la récurrence suivante: T (n) = 3T (bn/4c) + Θ(n2 )
Sans perte de généralité, nous allons créer un arbre récursif
pour la récurrence T (n) = 3T (n/4) + cn2 .
17 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Exemple d’utilisation
Soit la récurrence suivante: T (n) = 3T (bn/4c) + Θ(n2 )
Sans perte de généralité, nous allons créer un arbre récursif
pour la récurrence T (n) = 3T (n/4) + cn2 .
La figure ci-dessous montre le tracé progressif de l’arbre
récursif associé à T (n) = 3T (n/4) + cn2
17 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Exemple d’utilisation
Soit la récurrence suivante: T (n) = 3T (bn/4c) + Θ(n2 )
Sans perte de généralité, nous allons créer un arbre récursif
pour la récurrence T (n) = 3T (n/4) + cn2 .
La figure ci-dessous montre le tracé progressif de l’arbre
récursif associé à T (n) = 3T (n/4) + cn2
Pour des raisons de commodité, l’on suppose que n est une
puissance exacte de 4.
17 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Tracé de l’arbre récursif
cn2
T (n/4) T (n/4) T (n/4)
cn2
c(n/4)2 c(n/4)2 c(n/4)2
T (n/16) T (n/16) T (n/16) T (n/16) T (n/16) T (n/16) T (n/16) T (n/16) T (n/16)
18 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
cn2
c(n/4)2 c(n/4)2 c(n/4)2
c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2 c(n/16)2
T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1) T (1)
19 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Commentaire
Le terme cn2 situé sur la racine représente le coût au niveau
supérieur de la récursivité.
20 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Commentaire
Le terme cn2 situé sur la racine représente le coût au niveau
supérieur de la récursivité.
Les trois sous-arbres de la racine représentent les coûts induits
par les sous-problèmes de taille n/4.
20 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Commentaire
Le terme cn2 situé sur la racine représente le coût au niveau
supérieur de la récursivité.
Les trois sous-arbres de la racine représentent les coûts induits
par les sous-problèmes de taille n/4.
Chaque nœud de l’arbre est décomposé en ses parties
constitutives, telles que déterminées par la récurrence.
20 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Commentaire
Le terme cn2 situé sur la racine représente le coût au niveau
supérieur de la récursivité.
Les trois sous-arbres de la racine représentent les coûts induits
par les sous-problèmes de taille n/4.
Chaque nœud de l’arbre est décomposé en ses parties
constitutives, telles que déterminées par la récurrence.
Convergence: comme la taille du sous-problème décroît à
mesure que l’on s’éloigne de la racine, on finira par atteindre
une condition aux limites.
20 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
De la racine aux feuilles
À quelle distance de la racine cela se produira-t-il ?
21 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
De la racine aux feuilles
À quelle distance de la racine cela se produira-t-il ?
La taille de sous-problème pour un nœud situé à la profondeur
i est de n/4i .
21 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
De la racine aux feuilles
À quelle distance de la racine cela se produira-t-il ?
La taille de sous-problème pour un nœud situé à la profondeur
i est de n/4i .
Donc, la taille de sous-problème prendra la valeur n = 1 quand
n/4i = 1 ou, de manière équivalente, quand i = log4 n.
21 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
De la racine aux feuilles
À quelle distance de la racine cela se produira-t-il ?
La taille de sous-problème pour un nœud situé à la profondeur
i est de n/4i .
Donc, la taille de sous-problème prendra la valeur n = 1 quand
n/4i = 1 ou, de manière équivalente, quand i = log4 n.
Par conséquent, l’arbre a log4 n + 1 niveaux (0, 1, 2, · · · , log4 n).
21 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
coût et nombre de noeuds par niveau
Chaque niveau a trois fois plus de nœuds que le niveau
immédiatement supérieur, de sorte que le nombre de nœuds
de profondeur i est 3i .
22 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
coût et nombre de noeuds par niveau
Chaque niveau a trois fois plus de nœuds que le niveau
immédiatement supérieur, de sorte que le nombre de nœuds
de profondeur i est 3i .
Comme la taille du sous-problème diminue d’un facteur 4
quand on descend d’un niveau, chaque nœud de profondeur i,
pour i = 0, 1, 2, · · · , log4 n − 1, possède un coût de c(n/4i )2 .
22 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
coût et nombre de noeuds par niveau
Chaque niveau a trois fois plus de nœuds que le niveau
immédiatement supérieur, de sorte que le nombre de nœuds
de profondeur i est 3i .
Comme la taille du sous-problème diminue d’un facteur 4
quand on descend d’un niveau, chaque nœud de profondeur i,
pour i = 0, 1, 2, · · · , log4 n − 1, possède un coût de c(n/4i )2 .
En multipliant, on voit que le coût total pour l’ensemble des
nœuds de profondeur i, pour i = 0, 1, 2, · · · , log4 n − 1, vaut
3i c(n/4i )2 = (3/16)i cn2 .
22 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Dernier niveau
Le dernier niveau de profondeur log4 n, a 3log4 n = nlog4 3 nœuds.
23 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Dernier niveau
Le dernier niveau de profondeur log4 n, a 3log4 n = nlog4 3 nœuds.
Chaque noeud a un coût T (1).
23 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Dernier niveau
Le dernier niveau de profondeur log4 n, a 3log4 n = nlog4 3 nœuds.
Chaque noeud a un coût T (1).
Coût total du dernier niveau: nlog4 3 T (1) = Θ(nlog4 3 ).
23 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Coût global de l’arbre
3 2 3 3
T (n) = cn2 + cn + ( )2 cn2 + · · · + ( )log4 n−1 cn2 + Θ(nlog4 3 )
16 16 16
log4 n−1
X 3 i 2
= ( ) cn + Θ(nlog4 3 )
16
i=0
(3/16)log4 n − 1 2
= cn + Θ(nlog4 3 )
(3/16) − 1
24 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Coût global majoré par la somme de la série
log4 n−1 ∞
X 3 X 3
T (n) = ( )i cn2 + Θ(nlog4 3 ) < ( )i cn2 + Θ(nlog4 3 )
16 16
i=0 i=0
1
= cn2 + Θ(nlog4 3 )
1 − (3/16)
16 2
= cn + Θ(nlog4 3 ) = O(n2 )
13
25 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Usage de la méthode de substitution
Conjecture: T (n) = O(n2 ) est une borne supérieure de la
récurrence T (n) = 3T (bn/4c + Θ(n2 ).
26 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Usage de la méthode de substitution
Conjecture: T (n) = O(n2 ) est une borne supérieure de la
récurrence T (n) = 3T (bn/4c + Θ(n2 ).
Montrer que T (n) ≤ dn2 pour une certaine constante d > 0.
26 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Calcul et conjecture
Usage de la méthode de substitution
Conjecture: T (n) = O(n2 ) est une borne supérieure de la
récurrence T (n) = 3T (bn/4c + Θ(n2 ).
Montrer que T (n) ≤ dn2 pour une certaine constante d > 0.
En utilisant la même constante c > 0 que précédemment, on a:
T (n) ≤ 3T (bn/4c) + Θ(n2 ) ≤ 3dbn/4c2 + cn2
3
≤ 3d(n/4)2 + cn2 = dn2 + cn2 ≤ dn2 ,
16
La dernière étape étant vraie si d ≥ (16/13)c.
26 on 34
La méthode de l’arbre récursif
Méthode de l’arbre récursif
Synthèse dans un exemple
De Erik D. Demaine, Charles E. Leiserson
27 on 34
La méthode générale
Méthode générale
Récurrence
La méthode générale s’applique aux récurrences de la forme:
T (n) = aT (n/b) + f (n), (2)
où a ≥ 1, b > 1 et f (n) est une fonction asymptotiquement
positive.
28 on 34
La méthode générale
Méthode générale
Commentaire
La récurrence 2 décrit le temps d’exécution d’un algorithme qui
divise un problème de taille n en a sous-problèmes, chacun de
taille n/b.
29 on 34
La méthode générale
Méthode générale
Commentaire
La récurrence 2 décrit le temps d’exécution d’un algorithme qui
divise un problème de taille n en a sous-problèmes, chacun de
taille n/b.
a et b étant des constantes positives.
29 on 34
La méthode générale
Méthode générale
Commentaire
La récurrence 2 décrit le temps d’exécution d’un algorithme qui
divise un problème de taille n en a sous-problèmes, chacun de
taille n/b.
a et b étant des constantes positives.
Les a sous-problèmes sont résolus récursivement, chacun
dans un temps T (n/b).
29 on 34
La méthode générale
Méthode générale
Commentaire
La récurrence 2 décrit le temps d’exécution d’un algorithme qui
divise un problème de taille n en a sous-problèmes, chacun de
taille n/b.
a et b étant des constantes positives.
Les a sous-problèmes sont résolus récursivement, chacun
dans un temps T (n/b).
Le coût induit par la décomposition du problème et la
combinaison des résultats des sous-problèmes est décrit par la
fonction f (n).
29 on 34
La méthode générale
Théorème
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et
soit T (n) définies pour les entiers positifs par la récurrence
T (n) = aT (n/b) + f (n),
où l’on interprète n/b comme signifiant bn/bc ou dn/be. T (n) peut
alors être bornée asymptotiquement de la façon suivante.
1. Si f (n) = O(nlogb a− ) pour une constante > 0, alors
T (n) = Θ(nlogb a ).
2. Si f (n) = Θ(nlogb a logk n), pour une constante k ≥ 0, alors
T (n) = Θ(nlogb a logk +1 n) .
3. Si f (n) = Ω(nlogb a+ ) pour une constante > 0, et si
af (n/b) ≤ cf (n) pour une constante c < 1, et pour tout n
suffisamment grand, alors T (n) = Θ(f (n)).
30 on 34
La méthode générale Trois cas usuels
Méthode générale
Comparaison de fonctions
Dans chacun des trois cas, on compare la fonction f (n) à la
fonction nlogb a .
31 on 34
La méthode générale Trois cas usuels
Méthode générale
Comparaison de fonctions
Dans chacun des trois cas, on compare la fonction f (n) à la
fonction nlogb a .
Intuitivement, la solution de la récurrence est déterminée par la
plus grande des deux fonctions.
31 on 34
La méthode générale Trois cas usuels
Méthode générale
Comparaison de fonctions
Cas 1 Dans ce cas, non seulement f (n) doit être plus petite
que nlogb a , mais elle doit être plus petite
polynomialement. Autrement dit, f (n) doit être
asymptotiquement inférieure à nlogb a d’un facteur n ,
pour une constante > 0.
Cas 2 Les deux fonctions croissent avec des taux similaires.
Cas 3 Dans ce cas, non seulement f (n) doit être plus
grande que nlogb a , mais elle doit être plus grande
polynomialement et, en outre, satisfaire à la condition
de dite de régularité selon laquelle
af (n/b) ≤ cf (n).
32 on 34
La méthode générale Application de la méthode générale
Méthode générale
Exemples
1. T (n) = 4T (n/2) + n
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n
Cas 1: f (n) = O(n2− ) pour = 1. T (n) = Θ(n2 )
2. T (n) = 4T (n/2) + n2
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n2
Cas 2: f (n) = Θ(n2 log0 n) c’est-à-dire k = 0.
T (n) = Θ(n2 log n)
3. T (n) = 4T (n/2) + n3
a = 4, b = 2 =⇒ nlogb a = n2 ; f (n) = n3
Cas 3: f (n) = Ω(n2+ ) pour = 1 et 4(n/2)3 ≤ cn3 ( condition
de régularité) pour c = 1/2 . T (n) = Θ(n3 )
33 on 34
La méthode générale Application de la méthode générale
Fin du chapitre
Merci de votre Attention
34 on 34
