Chapitre 2

Fondements de l’analyse des algorithmes

Mario Marchand IFT-3001 1

 Aperçu du chapitre

n Nous présenterons d’abord le cadre que nous utiliserons pour

analyser l’efficacité des algorithmes. Les points importants sont:
n Comment exprimer la taille des instances d’un problème

n Comment exprimer le temps d’exécution d’un algorithme d’une

manière qui soit indépendante de son implémentation et de la

machine utilisée pour exécuter l’algorithme
n L’importance de l’ordre de croissance du temps d’exécution d’un

algorithme
n Les notions d’analyse en pire cas, meilleur cas et cas « moyen ».

n Ensuite nous introduirons la notation asymptotique qui sera utilisée

pour exprimer l’ordre de croissance du temps d’exécution d’un
algorithme en fonction de la taille des instances.
n Finalement, nous examinerons les méthodes d’analyse des
algorithmes récursifs et non récursifs.

Mario Marchand IFT-3001, Chapitre 2 2

 Efficacité d’utilisation des ressources

n « Analyser un algorithme » signifie habituellement examiner et étudier

un algorithme en vue de déterminer rigoureusement son efficacité
n Un algorithme est efficace lorsqu’il utilise peu de ressources
n Les deux principales ressources habituellement utilisées par un
algorithme sont:
n L’espace mémoire

n Le temps d’exécution (le temps requis pour obtenir une réponse)

n Le temps d’exécution est habituellement l’élément déterminant (le

facteur limitatif) de la performance d’un algorithme.

n Dans ce cours, nous nous intéressons donc presque exclusivement au

temps d’exécution requis par les algorithmes
n Mais les méthodes que nous introduirons (ex.: notation
asymptotique) s’appliquent également à l’analyse des autres
ressources utilisées (comme l’espace mémoire)

Mario Marchand IFT-3001, Chapitre 2 3

 Temps d’exécution et opérations élémentaires

Nous désirons exprimer le temps d’exécution d’un algorithme de manière à ce

que cette expression caractérise l’algorithme et non pas l’implémentation, le
langage de programmation ou la machine utilisée.
n Ceci est possible en vertu du principe d’invariance: deux implémentations

différentes du même algorithme ont un temps (réel) d’exécution qui ne

diffère que d’une constante multiplicative
n Nous définissons alors le temps d’exécution d’un algorithme (sur une instance
donnée) comme étant le nombre d’opérations élémentaires effectuées par
l’algorithme (sur cette instance)
n Une opération élémentaire est une opération dont le temps d’exécution est
majoré (c’est-à-dire borné supérieurement) par une constante qui dépend
uniquement de l’implémentation, du langage de programmation ou de la
machine utilisée.
n Cette constante doit être la même pour toutes les instances possibles du

problème
n Chaque opération élémentaire comptera donc pour une seule unité de temps
(quelle que soit cette opération élémentaire)

Mario Marchand IFT-3001, Chapitre 2 4

 Opérations élémentaires

n Exemples d’opérations élémentaires:

n Opération arithmétique (addition, soustraction, multiplication…)
entre deux nombres lorsque la taille de ces nombres est bornée
par une constante k. Ex:
n Entiers occupant k bits (ou occupant au plus k bits)

n Réels points flottants codés sur k bits (ou occupant au plus k

bits)
n Comparaison entre deux objets de taille bornée. Ex:

n Caractères codés sur k bits

n Nombres codés sur k bits (ou utilisant au plus k bits)

n Affectations d’une valeur à une variable (utilisant au plus k bits)

n En résumé: une opération élémentaire implique toujours la

manipulation d’un certain nombre « d’objets ». Il faut alors que
n Le nombre d’objets en cause soit majoré par une constante

n La taille de chaque objet soit majorée par une constante

n Ces constantes ne doivent pas dépendre de la taille de l’instance

Mario Marchand IFT-3001, Chapitre 2 5

 La taille d’une instance

n L’entrée d’un algorithme est une instance: c.-à-d. un exemplaire du

problème que l’algorithme tente de solutionner
n La sortie est la solution du problème pour cette instance

n Nous désirons exprimer le temps d’exécution d’un algorithme (c.-à-d.

son nombre d’opérations élémentaires effectuées) en fonction de la
taille de l’instance
n La taille de l’instance est la taille de l’espace mémoire occupée par
l’instance exprimée en unités «naturelles » pour le problème en cause.
Exemples:
n Pour un problème de tri

n la taille de l’instance est le nombre d’éléments à trier (peu

importe la taille des éléments à trier pourvu qu’elle soit fixe)

n Pour le problème de calculer le produit de deux matrices n × n

n La taille de cette instance est le nombre d’éléments donc 2n .

2

n Mais on préfère généralement exprimer le temps d’exécution

en fonction de n.

Mario Marchand IFT-3001, Chapitre 2 6

 La taille d’une instance (suite)

n Autre exemple:
n Pour le problème de déterminer pgcd(m,n) le plus grand commun

diviseur entre deux entiers m et n

n La taille de l’instance est 2 lorsque chaque entier utilise

toujours au plus k bits (exemple k=32)

n Mais, dans ce cas, on ne permet pas à la taille des

instances de varier. Le problème que l’algorithme tente de

solutionner est alors trivial…
n La taille de cette instance est ⎡logb(m+1)⎤ + ⎡logb(n+1)⎤ lorsque

la taille de m et n n’est pas bornée et que m et n sont exprimés

en base b (voir exercices série 1).
n Le choix de la base modifie la taille seulement par un facteur

multiplicatif, car loga(n) = loga(b) × logb(n)

n (pourvu que a et b soient tous les deux supérieurs à 1)

Mario Marchand IFT-3001, Chapitre 2 7

 Opération de base d’un algorithme

n Nous désirons exprimer le temps d’exécution d’un algorithme en

fonction de la taille de l’instance
n Pour cela il faut, en principe, compter le nombre d’opérations
élémentaires effectuées par l’algorithme
n Ceci nous donnera le temps d’exécution (à une constante près)

n Une autre façon de procéder est d’identifier une opération de base

(parfois appelée instruction baromètre) pour l’algorithme
n Une opération de base d’un algorithme est une opération élémentaire
qui, à une constante près, est effectuée au moins aussi souvent que
n’importe quelle autre opération élémentaire de l’algorithme
n Nous ne sommes pas obligés de choisir une opération qui est

exécutée au moins aussi souvent que n’importe quel autre. Il suffit

qu’elle le soit à une constante près (qui ne croît pas avec la taille
de l’instance)

Mario Marchand IFT-3001, Chapitre 2 8

 Opération de base d’un algorithme (suite)

n Il est généralement assez simple d’identifier une opération de base

pour un algorithme, car la nature du problème qu’il tente de résoudre
nous suggère souvent l’opération contribuant le plus au temps
d’exécution

n Exemples:
n Pour les algorithmes de tri (par comparaison), l’opération de base

est la comparaison de deux valeurs (ou de deux clés)

n Pour la multiplication de matrices, l’opération de base est la

multiplication de deux nombres

n Pour l’algorithme d’Euclide qui détermine le plus grand commun

diviseur entre deux entiers m et n, l’opération de base est m mod n

n Et plusieurs autres exemples à venir dans le cours …

Mario Marchand IFT-3001, Chapitre 2 9

 Temps d’exécution et opération de base

n Soit C(n) le nombre de fois que l’opération de base (choisie) est

effectuée par l’algorithme sur une instance de taille n
n Soit T(n) le nombre d’opérations élémentaires effectuées par
l’algorithme sur une instance de taille n (c.-à-d. le temps d’exécution)
n Puisque chaque opération élémentaire i présente dans l’algorithme est
exécutée au plus kiC(n) fois (par la définition d’une opération de base)
n Et puisque tout algorithme possède un nombre fini R d’opérations qui
ne varie pas avec la taille de l’instance, nous avons:

n Où K est une constante qui ne varie pas avec la taille n de l’instance.

n Le temps d’exécution T(n) de tout algorithme est donc donné par C(n)
à une constante près

Mario Marchand IFT-3001, Chapitre 2 10

 L’ordre de croissance du temps d’exécution

n Pour déterminer le temps d’exécution d’un algorithme sur une instance de

taille n, il suffit alors de calculer C(n)
n Le tableau suivant met en évidence l’importance du comportement
asymptotique de C(n) : son ordre de croissance lorsque n→∞

Mario Marchand IFT-3001, Chapitre 2 11

 Remarques sur la croissance des fonctions

n La fonction n croît beaucoup plus rapidement que log(n)

n Lorsque l’on double la valeur de n :
n lg(n) → lg(2) + lg(n) = 1 + lg(n)

n n → 2n

n n → 4n
2 2

n n → 8n
3 3

n 2 → (2 )
n n 2

n La fonction n! croît beaucoup plus rapidement que l’ordre 2n

n Ceci est mis en évidence par la formule de Stirling:

n Un algorithme dont le temps d’exécution croît exponentiellement rapidement

(ou plus) peut généralement être utilisé uniquement sur de très petites
instances.

Mario Marchand IFT-3001, Chapitre 2 12

 Pires cas et meilleurs cas

n Le temps d’exécution d’un algorithme est donné par C(n): le nombre de

fois que l’opération de base est exécutée sur une instance de taille n.
n Pour la majorité des algorithmes, C(n) ne dépend pas uniquement
de la taille n de l’instance, mais de l’instance elle-même
n Dans ces circonstances, il existe plusieurs instances

différentes (mais de même taille n) donnant un temps

d’exécution différent.
n Dans ces circonstances, il convient d’identifier:

n Le(s) pire(s) cas (de taille n) dont le temps d’exécution sera

donné par Cworst(n)

n Le(s) meilleur(s) (de taille n) cas dont le temps d’exécution sera

donné par Cbest(n)

n Ainsi nous aurons: Cbest(n) ≤ C(n) ≤ Cworst(n) pour toute instance de

taille n

Mario Marchand IFT-3001, Chapitre 2 13

 Pires cas et meilleurs cas (suite)

n Dénotons le temps d’exécution sur l’instance x par C(x)

n Dénotons la taille de l’instance x par |x|

n Le temps d’exécution en pire cas Cworst(n) est donné par:

n Le temps d’exécution en meilleur cas Cbest(n) est donné par:

n Notez que les opérations min et max se font sur toutes les instances x
dont la taille est n (et non pas sur toutes les instances peu importe
leur taille).

Mario Marchand IFT-3001, Chapitre 2 14

 Exemple: recherche séquentielle

ALGORITHME RechSeq(A[0..n-1],K) n Les pires cas sont obtenus sur les

instances où l’on doit tester les n
// Retourne le plus petit index j tel éléments
// que A[j] = K n c.-à-d. lorsque

j←0 A[j] ≠ K ∀ j ∈ {0..n-2}

n Dans ces cas, l’opération de base
while j < n and A[j] ¹ K do est exécutée n fois
j←j+1 n Alors Cworst(n) = n

if j < n return j
n Les meilleurs cas sont obtenus sur
else return -1 les instances ayant A[0] = K
n Dans ces cas, l’opération de base
n L’opération de base de choix est le est exécutée 1 fois
prédicat A[j] ≠ K n Alors Cbest(n) = 1
n Mais notez que le prédicat j < n est
exécutée une fois de plus lorsque
n Donc, pour toute instance de taille
A[j] ≠ K ∀ j.
n, le temps d’exécution de cet
algorithme est compris entre 1 et n.

Mario Marchand IFT-3001, Chapitre 2 15

 Analyse du cas « moyen »

n On désire obtenir le temps d’exécution pour le cas « typique » : c’est ce

que l’on entend normalement par le cas « moyen »
n Mais ce type d’analyse détermine plutôt le temps d’exécution moyen: la
moyenne des temps d’exécution sur toutes les instances de taille n.
n Soit C(x) le temps d’exécution sur l’instance x.
n Dénotons la taille de l’instance x par |x|. Nous nous intéressons à
toutes les instances x telles que |x| = n.
n Le temps d’exécution moyen Cavg(n) des instances de taille n est alors
donné par l’espérance des temps d’exécution:

n P(x) = probabilité d’observer l’instance x (parmi les instances de taille n)

n Pour calculer Cavg(n) , il faut donc fournir une distribution de probabilité
« réaliste » sur les instances.
Mario Marchand IFT-3001, Chapitre 2 16
 Exemple d’analyse du cas « moyen »

n Illustrons la méthode sur l’algorithme de recherche séquentielle.

n Définissons notre distribution de probabilité comme suit:

n Supposons que l’on a une probabilité p d’avoir K ∈ A[0..n-1] (et une

probabilité 1-p d’avoir K Ï A[0..n-1]).

n Lorsque K ∈ A[0..n-1], supposons que chaque position j soit

équiprobable pour K. Puisque l’on a n éléments, chaque position j

possède la même probabilité 1/n.

n Soit: C1avg(n) = la moyenne des temps d’exécution quand K ∈ A[0..n-1]

n Soit: C0avg(n) = la moyenne des temps d’exécution quand K Ï A[0..n-1]
n Nous avons alors:
Cavg(n) = p C1avg(n) + (1-p) C0avg(n)

Mario Marchand IFT-3001, Chapitre 2 17

 Exemple d’analyse du cas « moyen » (suite)

n Nous avons que C0avg(n) = n car, dans tous ces cas, l’opération de
base est exécutée n fois.
n Lorsque K ∈ A[0..n-1], chaque position j possède la même probabilité
d’occupation = (1/n)
n Lorsque K=A[j], l’opération de base est exécutée 1+j fois. Alors:

n Alors:

Mario Marchand IFT-3001, Chapitre 2 18

 Exemple d’analyse du cas « moyen » (suite)

n Ce résultat caractérise « raisonnablement » le cas « moyen », car:

n Cavg(n) = (n+1)/2 lorsque p=1

n En moyenne, K se trouve au milieu du tableau (si K∈A[0..n-1])

n Cavg(n) = n lorsque p=0 (lorsque K Ï A[0..n-1])

n Ainsi Cavg(n) nous donne une meilleure idée du comportement

« typique » sur une instance « quelconque » de l’algorithme que le
résultat pour Cworst(n) et Cbest(n)
n C’est habituellement le cas si la distribution utilisée n’est pas trop

« irréaliste »
n Nous verrons que certains algorithmes (ex.: le tri rapide) donnent un
comportement asymptotique pour Cavg(n) qui est nettement
avantageux par rapport à celui de Cworst(n)
n Il est donc en général important de déterminer Cavg(n), car Cworst(n) est
peut-être trop « pessimiste »
n Mais c’est généralement plus difficile d’obtenir Cavg(n)

Mario Marchand IFT-3001, Chapitre 2 19

 Notation asymptotique : motivation

n Nous spécifierons l’efficacité d’un algorithme à l’aide des fonctions

Cbest(n), Cworst(n) et Cavg(n) (où n = taille de l’instance)

n Ces fonctions caractérisent le temps d’exécution à une constante près

n De plus, l’élément déterminant est le comportement asymptotique de ces

fonctions : c.-à-d., leur comportement lorsque n→∞

n Nous exprimerons alors ces fonctions à l’aide d’une notation, appelée

notation asymptotique qui a pour effet de regrouper sous une même
classe toutes les fonctions ayant le même ordre de croissance en n

Mario Marchand IFT-3001, Chapitre 2 20

 Notation asymptotique : motivation (suite)

n Nous pourrions nous objecter à effectuer l’analyse asymptotique de

C(n) en prétextant qu’une constante multiplicative peut parfois être plus
importante en pratique que son comportement asymptotique
n Exemple: un algorithme dont C(n) = n3 exécutera plus rapidement

qu’un autre algorithme dont C(n) = 106n2 lorsque n <106

n Mais de tels cas sont très rares et les constantes multiplicatives ne

sont généralement pas « astronomiques ».

n L’élément déterminant pour C(n) est donc son comportement
asymptotique

n Puisque que la taille n d’une instance est toujours un entier naturel et

que le temps d’exécution est toujours un nombre réel non négatif, nous
nous intéressons uniquement aux fonctions N → R+
n Dans ce qui suit, t(n), f(n) et g(n) désignent de telles fonctions

Mario Marchand IFT-3001, Chapitre 2 21

 Notation O (grand oh)

n La fonction t(n) appartient à O(g(n)), c.-à-d. t(n) ∈ O(g(n)), ssi il existe

une constante positive c et un entier positif n0 tel que t(n) ≤ c∙g(n) ∀ n ≥
n0

Mario Marchand IFT-3001, Chapitre 2 22

 Notation O (suite)

n Alors O(g(n)) est un ensemble de fonctions. C’est l’ensemble suivant:

n Exemples (faciles):
n 5.4 n2 ∈ O(n2), car 5.4 n2 ≤ 6 n2 ∀ n≥ 0

n n(n+1) ∈ O(n2), car n(n+1) = n2 + n ≤ 2n2 ∀ n≥1

n 5n+3 ∈ O(n), car 5n+3 ≤ 5n + n = 6n ∀ n ≥ 3

n 5n+3 ∈ O(n2), car 5n+3 ≤ 5n2 + 3n2 = 8n2 ∀ n ≥ 1

n 0.001n2 Ï O(n), car ∄ c,n0 : 0.001n2 ≤ cn ∀ n ≥ n0,

n mais 0.001n ∈ O(n ), car 0.001n ≤ n

2 2 2 2 ∀ n ≥ 0

n Lemme: Si t(n) ∈ O(n) alors t(n) ∈ O(n2).

n Preuve: t(n)∈ O(n) ⇒ ∃ c, n0 : t(n) ≤ cn ∀n ≥ n0. Or cn ≤ cn2

∀ n≥1. Alors t(n) ≤ cn2 ∀ n ≥ n0. CQFD.

n Puisqu’il existe t(n) : t(n) ∈ O(n2) et t(n) Ï O(n). On a O(n) ⊂ O(n2).

Mario Marchand IFT-3001, Chapitre 2 23

 Notation W (grand oméga)

n La fonction t(n) appartient à W(g(n)), c.-à-d. t(n) ∈ W(g(n)), ssi il existe

une constante positive c et un entier positif n0 tel que t(n) ≥ c∙g(n) ∀n ≥
n0

Mario Marchand IFT-3001, Chapitre 2 24

 Notation W (suite)

n Alors W(g(n)) est un ensemble de fonctions. C’est l’ensemble suivant:

n Exemples (faciles):
n 0.01 n2 ∈ W(n2), car 0.01 n2 ≥ 0.001 n2 ∀ n ≥ 0

n 5n-3 ∈ W(n), car 5n-3 ≥ 5n – n = 4n ∀ n ≥ 3

n n(n-1) ∈ W(n2), car n(n-1) = n2-n ≥ n2 – 0.5n2 = 0.5n2 ∀ n ≥ 2

n n2 ∈ W(n), car n2 ≥ n ∀ n ≥ 1

n 100n Ï W(n2), car ∄ c,n0 : 100n ≥ cn2 ∀ n ≥ n0

n Lemme de dualité entre O et W: f(n) ∈ O(g(n)) , g(n) ∈ W(f(n)).

n Preuve:

n f(n) ∈ O(g(n)) ⇔ ∃ c, n0 : f(n) ≤ cg(n) ∀ n ≥ n0.

n ⇔ ∃ c, n0 : g(n) ≥ (1/c) f(n) ∀ n ≥ n0..

n ⇔ g(n) ∈ W(f(n)). CQFD.

Mario Marchand IFT-3001, Chapitre 2 25

 Notation Q (grand thêta)

n Supposons que t(n) ∈ W(f(n)) et t(n) ∈ O(g(n)). Nous disons alors que:
n f(n) est une borne asymptotique inférieure pour t(n)

n g(n) est une borne asymptotique supérieure pour t(n)

n Si la même fonction g(n) est à la fois une borne asymptotique inférieure

et supérieure pour t(n) nous disons qu’elle est la borne asymptotique
exacte pour t(n).
n Nous écrivons alors t(n) ∈ Q(g(n))

n Alors: t(n) ∈ Q(g(n)) ⇔ t(n) ∈ W(g(n)) et t(n) ∈ O(g(n))

n Alors: Q(g(n)) = W(g(n)) ∩ O(g(n))
n Exemple: n(n-1) ∈ Q(n2). Preuve:

n n(n-1) = n – n ≥ n - 0.5n = 0.5n ∀ n ≥ 2 ⇒ n(n-1) ∈ W(n )

2 2 2 2 2

n n(n-1) ≤ n ∀n ≥ 0 ⇒ n(n-1) ∈ O(n ).

2 2

n ⇒ n(n-1) ∈ Q(n ). CQFD.

2

Mario Marchand IFT-3001, Chapitre 2 26

 Notation Q (suite)

n Alors t(n)∈Q(g(n)) ⇔
(∃ c2,n2 : c2 g(n) ≤ t(n) ∀ n≥ n2) ⋀ (∃ c1,n1 : t(n) ≤ c1 g(n) ∀ n ≥ n1)
⇔ ∃ c1,c2,n0 : c2 g(n) ≤ t(n) ≤ c1 g(n) ∀ n≥ n0 (avec n0 = max{n1,n2})

n Certains utilisent cette dernière propriété pour définir Q(g(n)) qui

donne donc cet ensemble suivant de fonctions:

Mario Marchand IFT-3001, Chapitre 2 27

 Notation Q (suite)

Mario Marchand IFT-3001, Chapitre 2 28

 Quelques propriétés

n Les propriétés suivantes sont facilement démontrables:

n (utilisons G pour désigner W, O ou Q)

n Transitivité:
n f(n)∈ G(g(n)) ⋀ g(n) ∈ G(h(n)) ⇒ f(n) ∈ G(h(n))

n Réflexivité:
n f(n) ∈ G(f(n))

n Symétrie:
n f(n) ∈ Q(g(n)), g(n) ∈ Q(f(n))

n Donc seul Q défini une relation d’équivalence entre fonctions

n (les preuves de ces propriétés sont laissées en exercice au lecteur)

Mario Marchand IFT-3001, Chapitre 2 29

 Notation asymptotique et temps d’exécution

n Rappels:
n T(n) = le nombre d’opérations élémentaires effectuées par un

algorithme sur une instance de taille n (c.-à-d. le temps

d’exécution)
n C(n) = le nombre d’opérations de base effectuées par un

algorithme sur une instance de taille n

n Nous avions: C(n) ≤ T(n) ≤ K∙C(n) ∀ n ≥ 0 (où K = constante)

n Alors T(n) ∈ Q(C(n)). Alors T(n) et C(n) sont des mesures équivalentes
du temps d’exécution d’un algorithme

n Puisqu’il est (presque toujours) plus facile de trouver C(n) que de

trouver T(n), nous utilisons C(n) pour exprimer le temps d’exécution!

Mario Marchand IFT-3001, Chapitre 2 30

 Notation asymptotique et temps d’exécution (suite)

n Pour tout algorithme nous avons:

n Cworst(n) ∈ O(g(n)) ⇔ C(n) ∈ O(g(n))

n g(n) est donc une borne asymptotique supérieure du temps

d’exécution de l’algorithme
n Cbest(n) ∈ W(f(n)) ⇔ C(n) ∈ W(f(n))

n f(n) est donc une borne asymptotique inférieure du temps

d’exécution de l’algorithme
n Cworst(n) ∈ Q(f(n)) ⇒ C(n) ∈ O(f(n))

n Cbest(n) ∈ Q(f(n)) ⇒ C(n) ∈ W(f(n))

n Est-ce qu’une borne asymptotique exacte Q(f(n)) sur Cworst(n) nous

donne plus d’information qu’une borne asymptotique supérieure O(f(n))?

n Est-ce qu’une borne asymptotique exacte Q(f(n)) sur Cbest(n) nous donne
plus d’information qu’une borne asymptotique inférieure W(f(n)) ?

Mario Marchand IFT-3001, Chapitre 2 31

 Notation asymptotique et temps d’exécution (suite)

n La borne asymptotique exacte Q(f(n)) sur Cworst(n) et Cbest(n) nous

donne plus d’information que les bornes O(f(n)) et W(f(n)), car:
n Cworst(n) ∈ Q(f(n)) nous assure que f(n) est la borne asymptotique
supérieure pour C(n) qui est la plus faible qui soit (et donc la
meilleure). Nous n’avons pas cette garantie si nous avons
seulement Cworst(n) ∈ O(f(n))
n En effet si (par exemple) Cworst(n) ∈ O(n ), il est possible, qu’en
2

fait, nous ayons Cworst(n) ∈ Q(n) (car n ∈ O(n2))

n Cbest(n) ∈ Q(f(n)) nous assure que f(n) est la borne asymptotique

inférieure pour C(n) qui est la plus élevée qui soit (et donc la
meilleure). Nous n’avons pas cette garantie si nous avons
seulement Cbest(n) ∈ W(f(n))
n En effet si (par exemple) Cbest(n) ∈ W(n), il est possible, qu’en

fait, nous ayons Cbest(n) ∈ Q(n2) (car n2 ∈ W(n))

Mario Marchand IFT-3001, Chapitre 2 32

 Notation asymptotique et temps d’exécution (suite)

n Que pouvons-nous conclure de C(n) si Cworst(n) ∈ W(f(n)) ?

n Réponse: nous ne pouvons pas conclure que C(n) ∈ W(f(n)), car

Cbest(n) ∈ W(g(n)) avec f(n) ∈ W(g(n)) et la transitivité ne peut pas

s’effectuer pour conclure que C(n) ∈ W(f(n)). Nous ne pouvons pas
conclure également que C(n) ∈ O(f(n)).
n Une borne asymptotique inférieure sur Cworst(n) est donc très peu

informative, à elle seule, sur C(n)

n Que pouvons-nous conclure de C(n) si Cbest(n) ∈ O(f(n)) ?

n Réponse: nous ne pouvons pas conclure que C(n) ∈ O(f(n)), car

Cworst (n) ∈ O(g(n)) avec f(n) ∈ O(g(n)) et la transitivité ne peut pas

s’effectuer pour conclure que C(n) ∈ O(f(n)). Nous ne pouvons pas
conclure également que C(n) ∈ W(f(n)).
n Une borne asymptotique supérieure sur Cbest(n) est donc très peu

informative, à elle seule, sur C(n)

Mario Marchand IFT-3001, Chapitre 2 33

 La règle du maximum

n Utilisons G pour désigner W, O ou Q

n Théorème (règle du maximum):
t1(n) ∈ G(g1(n)) ⋀ t2(n) ∈ G(g2(n)) ⇒ t1(n) + t2(n) ∈ G(max{g1(n), g2(n)})
n Preuve (légèrement abrégée):
n t1(n) ∈ O(g1(n)) ⋀ t2(n) ∈ O(g2(n))

n ⇒ (t1(n) ≤ c1g1(n) ∀ n ≥ n1) ⋀ (t2(n) ≤ c2g2(n) ∀ n ≥ n2)

n ⇒ t1(n) + t2(n) ≤ c1g1(n) + c2g2(n) ∀ n ≥ n3 (avec n3 = max{n1,n2})

≤ c3(g1(n) + g2(n)) ∀ n ≥ n3 (avec c3 = max{c1,c2})

≤ 2c3max{g1(n), g2(n)} ∀ n ≥ n3
n ⇒ t1(n) + t2(n) ∈ O(max{g1(n), g2(n)})

n Similairement on démontre que:

t1(n)∈W(g1(n)) ⋀ t2(n)∈W(g2(n)) ⇒ t1(n)+t2(n) ∈ W(max{g1(n), g2(n)})

t1(n)∈Q(g1(n)) ⋀ t2(n) ∈Q(g2(n)) ⇒ t1(n)+t2(n) ∈ Q(max{g1(n), g2(n)})
n CQFD.

Mario Marchand IFT-3001, Chapitre 2 34

 L’utilité de la règle du maximum en algorithmique

n Supposons qu’un algorithme possède deux parties exécutées

consécutivement (l’une après l’autre)
n La première partie prend un temps C1(n)∈O(g1(n))

n La deuxième partie prend un temps C2(n)∈O(g2(n))

n Le temps total d’exécution C(n) sera alors donné par:

C(n) = C1(n)+C2(n) ∈ O(max{g1(n), g2(n)})
n C(n) est donc déterminé par la partie de l’algorithme ayant l’ordre de
croissance le plus élevé
n Exemple:
n supposons que pour déterminer si un tableau A de n éléments possède

des éléments identiques, nous trions d’abord A et qu’ensuite, nous

parcourions A une seule fois pour déterminer s’il existe i : A[i]=A[i+1].
n Supposons que notre algorithme de tri prends un temps C1(n)∈O(nlog(n))

n Puisque la recherche séquentielle prends C2(n)∈O(n), le temps total sera

de C(n) = C1(n) + C2(n) ∈ O(max{nlog(n), n}) = O(nlog(n)).

n Donc C(n)∈O(nlog(n)).

Mario Marchand IFT-3001, Chapitre 2 35

 Remarques sur la règle du maximum

n Nous pouvons l’utiliser un nombre constant de fois (indépendant de n).

n Exemple: O(n2 + n + log(n) ) = O(max{n2, n, log(n)}) = O(n2)

n Mais nous ne pouvons pas l’utiliser n fois. (ou f(n) fois)

n Exemple: O(n2) = O(n + n +…+ n (n fois)) ≠ O(max{n, n, …, n}) = O(n)

n Il ne doit pas y avoir de fonctions négatives parmi celles utilisées:

n Exemple: O(n) = O(n + n2 – n2) ¹ O(max{n, n2, -n2}) = O(n2)

Mario Marchand IFT-3001, Chapitre 2 36

 Utilisation des limites pour comparaison d’ordre

n Pour comparer la croissance de deux fonctions g(n) et f(n), il est

généralement plus pratique d’utiliser le théorème suivant (que
d’utiliser les définitions de W, O, Q):

n Lorsque f(n)∈Q(g(n)) nous disons que f(n) et g(n) ont le même ordre
de croissance.

n Lorsque f(n) ∈ O(g(n)) et f(n) Ï Q(g(n)) nous disons que l’ordre de

croissance de f(n) est strictement plus petit que celui de g(n)

n Lorsque f(n) ∈ W(g(n)) et f(n) Ï Q(g(n)) nous disons que l’ordre de

croissance de f(n) est strictement plus grand que celui de g(n)

Mario Marchand IFT-3001, Chapitre 2 37

 Exemples d’utilisation des limites

n Exemple: Comparez l’ordre de croissance de n(n-1) avec celui de n2.

n Solution:

n alors n(n-1) ∈ Q(n2). Donc n(n-1) et n2 ont le même ordre de croissance.

n Exemple: Comparez l’ordre de croissance de n! avec celui de 2n.

n Solution:

n Donc n! ∈ W(2n) et n! Ï Q(2n).

n Donc l’ordre de n! est strictement plus grand que celui de 2n.

Mario Marchand IFT-3001, Chapitre 2 38

 La règle de L’Hôpital

n Il arrive souvent que f(n) et g(n) → ∞ lorsque n → ∞. Dans ces cas nous
pouvons habituellement utiliser la règle de L’Hôpital :

n où f’(n) désigne la dérivée première de f évaluée à n.

n Cette règle s’applique aux formes 0/0 et ∞/∞

n Exemple: Comparez l’ordre de croissance de lg(n) avec celui de n1/2.

n Solution:

n Donc lg(n) ∈ O(n1/2) et lg(n) Ï Q(n1/2).

n Donc l’ordre de lg(n) est strictement plus petit que celui de n1/2.

Mario Marchand IFT-3001, Chapitre 2 39

 Les classes d’efficacité courantes en algorithmique

n L’ensemble des fonctions appartenant à Q(g(n)) définie la classe

d’efficacité g(n).
n Il existe une infinité de classes d’efficacité distinctes
n Exemple: Q(2n) ¹ Q(3n) ¹ Q(4n) … Q(n1/2) ¹ Q(n1/3) ¹ Q(n1/4) …

n Cependant, en algorithmique, on retrouve surtout les classes

d’efficacité suivantes:
n Classe 1 (constante): sont les algorithmes dont le temps

d’exécution demeure constant en fonction de n (quasi impossible)

n Classe log(n) (logarithmique): sont les algorithmes qui réduisent

n d’un facteur constant à chaque itération (sans devoir examiner

tous les éléments, sinon l’algorithme serait au moins linéaire)
n Classe n (linéaire): les algorithmes qui examinent chaque élément

un nombre constant de fois

n Classe n log(n): typique des algorithmes « diviser pour régner »

comme le tri fusion

Mario Marchand IFT-3001, Chapitre 2 40

 Les classes d’efficacité courantes en algorithmique (suite)

n Classe n2 (quadratique): typiquement les algorithmes constitués

de deux boucles imbriquées (ex.: tris élémentaires)
n Classe n3 (cubique): typiquement les algorithmes constitués de
trois boucles imbriquées (ex.: algorithmes d’algèbre linéaire)
n Classe 2n (exponentielle): typiquement les algorithmes examinant
tous les sous-ensembles des n éléments de l’instance.
n En fait, la classe exponentielle désigne l’ensemble de toutes

les classes kn
n Classe n! (factoriel): typique des algorithmes qui examinent
toutes les permutations des n éléments de l’instance

Mario Marchand IFT-3001, Chapitre 2 41

 Analyse des algorithmes non récursifs

n Beaucoup d’algorithmes sont non récursifs et ils sont généralement plus

simples à analyser que les algorithmes récursifs
n La difficulté mathématique « majeure » se limite souvent au calcul

d’une sommation
n Plan général d’analyse des algorithmes non récursifs:
n Déterminez la taille de l’instance à l’aide d’un (ou des) paramètre(s)

n Identifiez l’opération de base

n Déterminez si le nombre de fois que l’opération de base est

effectuée dépend uniquement de la taille de l’instance

n Si ça ne dépend pas uniquement de la taille de l’instance, il

faudra faire une analyse séparée des pires cas et des meilleurs
cas (et du cas moyen si c’est possible)
n Effectuez la sommation issue de cette (ou ces) analyse(s)

n Exprimez uniquement le(s) ordre(s) de croissance à l’aide de la

notation asymptotique

Mario Marchand IFT-3001, Chapitre 2 42

 Exemple d’un algorithme non récursif

n Considérons le problème de ALGORITHME ElemDiff(A[0..n-1])

déterminer si les n éléments d’un
// Entrée: tableau A de n éléments
tableau sont tous distincts
// Sortie: true si tous les éléments
n L’ensemble des instances est // sont distincts et false autrement
l’ensemble de tous les n-tuplets
d’éléments for i ← 0 to n - 2 do
n L’algorithme suivant solutionne for j ← i + 1 to n - 1 do
correctement ce problème
if A[i]=A[j] return false
n La taille de l’instance est le nombre
n d’éléments dans le tableau return true
n Car nous supposons ici que

chaque élément possède une n L’opération de base sera le prédicat

taille bornée par une constante de comparaison: A[i] = A[j]
n Cette opération est effectuée

au moins aussi souvent que

n’importe quelle autre. C’est
donc un choix valide

Mario Marchand IFT-3001, Chapitre 2 43

 Exemple d’un algorithme non récursif (suite)

n Le nombre de fois que l’opération de base est effectuée dépend de

l’existence (ou non) d’éléments identiques et, si c’est le cas, de leur
position dans le tableau
n Pour une taille n donnée, le nombre de fois que l’opération de base est
effectuée sera différent dans le pire cas et dans le meilleur cas.
n Les meilleurs cas sont ceux où A[0] = A[1], car, pour ces cas,
l’algorithme termine après une seule comparaison.
n Alors Cbest(n) = 1 ∈ Q(1)

n Les pires cas sont ceux où la comparaison A[i] = A[j] est effectuée un
nombre maximal de fois
n Cela se produit, entre autres, lorsque tous les éléments de A sont

distincts
n Cworst(n) sera donc donné par le nombre de fois que cette comparaison
est effectuée lorsque tous les n éléments sont distincts

Mario Marchand IFT-3001, Chapitre 2 44

 Exemple d’un algorithme non récursif (suite)

n Nous avons alors:

n Nous trouvons donc que Cworst(n) ∈ Q(n2)

n Nous nous sommes servis de la « formule » de sommation suivante:

Mario Marchand IFT-3001, Chapitre 2 45

 Borner une sommation par une intégrale

n Cette approche requiert donc l’utilisation d’un dictionnaire de formules

de sommation. Que faire si l’on a besoin d’une formule qui n’est pas
dans notre dictionnaire? Par exemple:

n En fait, puisque l’on ne s’intéresse qu’au comportement asymptotique,

nous n’avons pas besoin d’un dictionnaire de formules de sommation.
n Il suffit d’utiliser le théorème suivant qui nous donne une borne
inférieure et une borne supérieure d’une sommation:

Mario Marchand IFT-3001, Chapitre 2 46

 Preuve pour une fonction non décroissante

n Rappel: la fonction f(x) est non décroissante dans [a,b] ssi f(x) est
croissant ou constant pour tout x ∈ [a,b].
f(u) f(x)

f(l+1)

f(l)

l l+1 u u+1

n La somme des aires de chaque rectangle est inférieure ou égale à

l’aire sous f(x) entre l et u+1.

Mario Marchand IFT-3001, Chapitre 2 47

 Preuve pour une fonction non décroissante (suite)

f(x)
f(l)

f(u)

l-1 l u-1 u

n La somme des aires de chaque rectangle est supérieure ou égale à

l’aire sous f(x) entre l-1 et u.

Mario Marchand IFT-3001, Chapitre 2 48

 Borner une sommation par une intégrale (suite)

n Par exemple, puisque x4 est une fonction non décroissante, nous

avons: Z n
Pn
Z n+1
x4 dx  i4  x4 dx
0 i=1 1
h 5 n P
n h n+1
x 4 x5
) 5  i  5
0 i=1 1

n5
P
n
(n+1)5 1
) 5  i4  5 5
i=1

n5
P
n
(n+n)5
) 5  i4  5
i=1

n5
P
n
25 5
) 5  i4  5 n
i=1
P
n
) i4 2 ⇥(n5 )
i=1
n De la même manière, nous trouvons que:

Mario Marchand IFT-3001, Chapitre 2 49

 De retour à l’analyse de ElemDiff en pire cas

n Retournons à l’analyse en pire cas de l’algorithme ElemDiff où nous

avions:

n Puisque x est une fonction non décroissante, bornons la dernière

sommation par les deux intégrales:

Mario Marchand IFT-3001, Chapitre 2 50

 De retour à l’analyse de ElemDiff en pire cas (suite)

n Nous avons alors:

n Nous trouvons donc que Cworst(n) ∈ Q(n2) sans avoir utilisé un

dictionnaire de formules de sommation.

Mario Marchand IFT-3001, Chapitre 2 51

 Appels de fonction

n Souvent, un algorithme fait un ALGORITHME Compte(A[0..n-1],

appel à une fonction qui ne B[0..m-1])
s’exécute pas en temps // Entrée: 2 tableaux de n et m éléments
constant. // Sortie: Le nombre d’éléments dans B
n C’est le cas de l’algorithme qui se retrouvent dans A
Compte qui retourne le nombre count ← 0
d’éléments dans le vecteur B qui
for i ← 0 to m - 1 do
se retrouvent dans le vecteur A.
n La taille de l’instance est donnée if RechSeq(A, B[i]) ≥ 0 then
à la fois par les valeurs de m et count ← count + 1
de n. return count
n En meilleur cas, tous les
éléments dans B sont identiques
à A[0]
n En pire cas, aucun des éléments
dans B n’est dans A.
Mario Marchand IFT-3001, Chapitre 2 52
 Appels de fonction

n Puisque RechSeq n’est pas une instruction élémentaire s’exécutant en

temps Θ(1), nous ne pouvons pas inscrire la valeur 1 dans la
sommation.
n Il faut plutôt y inscrire le temps d’exécution de la fonction qui est
appelée.

m
X1 m
X1
Compte RechSeq
Cworst (n, m) = Cworst (n) = n = nm 2 ⇥(nm)
i=0 i=0
m
X1 m
X1
Compte RechSeq
Cbest (n, m) = Cbest (n) = 1 = m 2 ⇥(m)
i=0 i=0

Mario Marchand IFT-3001, Chapitre 2 53

 Appels de fonction

n Une autre façon de procéder est ALGORITHME Compte(A[0..n-1],

de remplacer l’appel de fonction B[0..m-1])
par le code de la fonction elle- // Entrée: 2 tableaux de n et m éléments
même. // Sortie: Le nombre d’éléments dans B
n On prend A[j] ¹ B[i] comme qui se retrouvent dans A
opération de base. count ← 0
for i ← 0 to m - 1 do
m
X1
<latexit sha1_base64="gq5TrGbzL9A1nSaHiytkmzwcjGs=">AAAICnicjVXLbtNAFL1pgZTwaAtLNgMRqJWgiisECKlS1QoJVhToS4pDcJxJO61f8gNaWf4DvoYdYssnsOEP4C84c+OkKUkcO4pz58y5577GcSdwVBQ3Gr8rc/NXrl6rLlyv3bh56/bi0vKd/chPQlvu2b7jh4cdK5KO8uRerGJHHgahtNyOIw86p9t6/+CzDCPle7vxeSBbrnXkqZ6yrRhQe+nXdjs1Q1dsvfqwm614j4W7Kh6JDWFGidtO1UYj+5i6T4xMGMI0a2L80mRXmMoT5u6xjK0VCICZyx68fT9Dtw+cMOAVBZrs7gH0LsX33NX2Ur2x1uBLjBtGbtQpv3b85flFMqlLPtmUkEuSPIphO2RRhE+TDGpQAKxFKbAQluJ9SRnV4JuAJcGwgJ7ifoRVM0c9rLVmxN42ojj4hvAU9BA+PnghbB1N8H7Cyhqdpp2yps7tHL+dXMsFGtMx0Fl+A2Z5vw6ysbCWYBbXHFOPXnCtCrUHjOgu2Hm0hLunKxQj1cdQCIBpu4v9ELbNnoN5CPaJuEcWZ6P3/zBTo3pt59yE/ubVeEC+cFddrtODegq8x1Poz0HPt8WojtCDv7YuGILqYAigITI7Qqditkc1imLprHTF0yIN9qfFufAviuLiLPjo4WgU3Y2IOyyHU+5z+7bmj65DWClnkeGjY+nTqoAq7EeM1gqz6DKSXcooHaLFFeg5xmO+A3SWrz3R1y7h60yM65SK60yM65SMq1kaOcsVps2rz2wPZ3XG2sXqAVR8fupSPhVF3Jj/6U55wmXOjX4CHSBvSuTRw9k5w163ULtXqh7Jz0I3/z+RM7vmlJiB4kkNnpkmsPu413mt7RZleKMY/78/xo399TXj2Zrx7ml9cyt/tyzQPXpAK9B6Tpv0mnZoj+zKy8qniqqcVL9Wv1W/V3/0qXOV3OcuXbqqP/8BsjqwAA==</latexit>

j←0
CBEST (n, m) = 1
i=0 while j < n and A[j] ¹ B[i] do
= m 2 ⇥(m) j←j+1
m
X1 nX1
CWORST (n, m) = 1 if j < n then
i=0 j=0 count ← count + 1
m
X1 return count
= n = nm 2 ⇥(nm)
i=0

Mario Marchand IFT-3001, Chapitre 2 54

 Autre exemple d’un algorithme non récursif

n Il arrive parfois que l’analyse du ALGORITHME Binary(n)

temps d’exécution d’un algorithme
// Entrée: entier positif de valeur n
non récursif ne nous donne pas une
// Sortie: le nombre de bits utilisés pour
sommation à effectuer.
// sa représentation binaire
count ← 1
n Considérez l’algorithme Binary(n)
pour calculer le nombre de bits de while n > 1 do
l’entier de valeur n.
count ← count + 1

n Utilisons la division par deux dans n ← ⎣n/2⎦

⎣n/2⎦ pour l’opération de base. return count

n Le nombre C(n) de fois que n De telles relations de récurrence

l’opération de base est effectuée émergent naturellement des
pour un entier de valeur n est algorithmes récursifs.
donnée par la récurrence:
C(n) = C(⎣n/2⎦) + 1 si n > 1
C(n) = 0 si n ≤ 1
Mario Marchand IFT-3001, Chapitre 2 55
 Analyse des algorithmes récursifs et résolution de récurrences

n Plan général d’analyse des algorithmes récursifs:

n Déterminez la taille de l’instance à l’aide d’un (ou des) paramètre(s)

n Identifiez l’opération de base

n Déterminez si le nombre de fois que l’opération de base est

effectuée dépend uniquement de la taille de l’instance

n Si ça ne dépend pas uniquement de la taille de l’instance, il

faudra faire une analyse séparée des pires cas et des meilleur
cas (et du cas moyen si c’est possible)
n Solutionnez la relation de récurrence issue de cette (ou ces)

analyse(s)
n Exprimez uniquement le(s) ordre(s) de croissance à l’aide de la

notation asymptotique

Mario Marchand IFT-3001, Chapitre 2 56

 Exemple: les tours de Hanoi

n Nous avons 3 tiges (tours) et n disques de tailles (rayons) distinctes

n Initialement: tous les disques sont sur la 1re tige en ordre de taille
n Le plus petit disque est au sommet

n Objectif: déplacer tous les disques (un à la fois) de la 1re tige à la troisième
tige en utilisant (possiblement) la seconde tige comme tige auxiliaire
n Contrainte: à tout moment, il ne peut pas y avoir un disque au-dessus d’un

autre disque de plus petite taille

n Solution pour n=1: nous pouvons déplacer l’unique disque directement de la
1re à la 3e tige

Mario Marchand IFT-3001, Chapitre 2 57

 Exemple: les tours de Hanoi (suite)

n La solution pour n > 1 est donnée par l’algorithme récursif suivant:

n (1) Déplacer d’abord les n-1 disques supérieurs de la tige 1 à la tige 2 en se

servant de la tige 3 comme tige auxiliaire

n (2) Déplacer le plus grand disque de la tige 1 à 3 (directement)
n (3) Déplacer les n-1 disques de la tige 2 à la tige 3 en se servant de la tige 1

comme tige auxiliaire

n Cet algorithme est correct pour n=1. S’il est correct pour n, il le sera pour n+1
(pour tout n ≥ 1). L’algorithme est donc correct pour tout n ≥ 1.

Mario Marchand IFT-3001, Chapitre 2 58

 Analyse de l’algorithme des tours de Hanoi

n La taille de l’instance = n (le nombre de disques)

n L’opération de base = déplacement d’un disque d’une tige à une autre
n Il existe une seule instance lorsque n est fixe. Le temps d’exécution
C(n) dépend donc uniquement de n.
n Le pire cas est identique au meilleur cas

n Déterminons alors C(n) : le nombre de déplacements effectués par

l’algorithme pour solutionner le problème avec n disques

n L’algorithme nous indique que:

n C(n) = C(n-1) + 1 + C(n-1) = 2C(n-1) + 1 ∀ n > 1 (la récurrence)

n Avec: C(1) = 1 (condition initiale)

n Tout changement apporté à la condition initiale (ex.: C(1) = 2) entraîne

une modification de la solution générée par la récurrence.
n La solution dépend de la condition initiale: il faut donc la spécifier

Mario Marchand IFT-3001, Chapitre 2 59

 Analyse de l’algorithme des tours de Hanoi (suite)

n Solutionnons cette récurrence par la méthode des substitutions à rebours

(« backward substitutions »)
n L’idée est d’exprimer la solution en fonction de la condition initiale

n C(n) = 2C(n-1) + 1
= 2[2C(n-2) + 1] +1 (car C(n-1) = 2C(n-2) + 1)
= 22C(n-2) + 2 + 1
= 22[2C(n-3) + 1] + 2 + 1 (car C(n-2) = 2C(n-3) + 1)
= 23C(n-3) + 22 + 2 + 1
= ….
= 2iC(n-i) + 2i-1 + 2i-2 + … + 2 + 1 ∀ i > 1
= 2n-1 C(1) + 2n-2 + … + 2 + 1 (en utilisant i = n-1)
= 2n-1 + 2n-2 + … + 2 + 1 (en utilisant C(1) = 1)
= 2n – 1 (série géométrique très connue; voir annexe A du manuel)
n Alors C(n) = 2n – 1 ∈ Q(2n) (ordre de croissance exponentiel)
n La concision d’un algorithme récursif n’est pas garante de son efficacité
n Mais, dans ce cas-ci, il semble qu’il soit impossible de faire mieux!

Mario Marchand IFT-3001, Chapitre 2 60

 Autre exemple d’algorithme récursif

n Considérons BinRec(n) qui est la ALGORITHME BinRec(n)

version récursive de Binary(n) // Entrée: entier positif de valeur n
n Opération de base: « +1 » // Sortie: le nombre de bits utilisés pour
n Autre possibilité: la division // sa représentation binaire
dans ⎣n/2⎦
If n = 1 return 1
n Le nombre C(n) d’opérations de else return BinRec(⎣n/2⎦) + 1
base effectuées par l’algorithme sur
un entier de valeur n est donné par
la récurrence:
C(n) = C(⎣n/2⎦) + 1 n Nous avons alors:
n Avec la condition initiale: C(2k) = C(2k-1) + 1
C(1) = 0 n Avec:
C(20) = 0
n Essayons d’abord de résoudre
seulement pour les valeurs de n
satisfaisant:
n = 2k pour k∈N

Mario Marchand IFT-3001, Chapitre 2 61

 Solution de l’algorithme récursif

n La méthode des substitutions à rebours donne:

n C(2k) = C(2k-1) + 1

= [C(2k-2) + 1] + 1 (car C(2k-1) = C(2k-2) + 1)

= C(2k-2) + 2
= [C(2k-3) + 1] + 2 (car C(2k-2) = C(2k-3) + 1)
= C(2k-3) + 3
…
= C(2k-i) + i (pour tout i > 0)
= C(20) + k (pour i = k)
=k (car C(20) = 0)
n Alors C(n) = lg(n) ∈ Q(log(n)) pour n = 2k.
n Or (voir pages suivantes) lg(n) est une fonction harmonieuse.
n On a alors (voir pages suivantes) C(n) ∈ Q(log(n)) ∀ n>1
n C(n) est donc linéaire en la taille de n (∀ n > 1). (Nous savions cela…)

Mario Marchand IFT-3001, Chapitre 2 62

 Fonctions harmonieuses

n Une fonction non négative f(n) est éventuellement non décroissante

ssi il existe n0 tel que f(n) est non décroissante dans [n0,∞)
n Exemples de fonctions éventuellement non décroissantes

n log(n) (avec n0 = 1)
n n
k ∀ k > 0 (avec n0 = 0)
n n log(n) (avec n0 = 0)
n 2 (avec n0 = 0)
n

n Une fonction éventuellement non décroissante est harmonieuse ssi

f(2n) ∈ Q(f(n))
n Exemples:
n log(n) est harmonieuse, car log(2n) = log(2) + log(n) ∈ Q(log(n))

n nk est harmonieuse, car (2n)k = 2k nk ∈ Q(nk)

n 2n n’est pas harmonieuse car 22n = (22)n = 4n Ï Q(2n)

n n! n’est pas harmonieuse, car (2n)! Ï Q(n!)

Mario Marchand IFT-3001, Chapitre 2 63

 La règle de l’harmonie

n Théorème: Si f(n) est harmonieuse alors f(bn) ∈ Q(f(n)) ∀ b ≥ 2.

n Preuve: voir annexe B du manuel (facultative)

n Théorème (règle de l’harmonie): Si C(n) est éventuellement non

décroissante, si f(n) est harmonieuse et si C(n) ∈ Q(f(n)) pour n = bk
avec k ∈ N alors C(n) ∈ Q(f(n)) ∀ n ∈ N
n Preuve: voir annexe B du manuel (facultative)

n Ce théorème est également valide pour O et W

n Application: pour un algorithme donnant un C(n) éventuellement non

décroissant, chaque fois que trouverons que C(n) ∈ G(f(n)) pour
n = bk, nous pourrons en conclure que C(n) ∈ G(f(n)) ∀ n lorsque f(n)
est harmonieuse. (ici G désigne O, W ou Q)
n C’est ce que nous avons fait pour l’analyse de BinRec(n)

Mario Marchand IFT-3001, Chapitre 2 64

 La suite de Fibonacci

n La suite de Fibonacci est constituée des nombres de Fibonacci:

n 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

n Elle fut introduite par Leonardo Fibonacci en 1202 et se trouve présente dans
la solution de nombreux problèmes
n La suite de Fibonacci est générée par la récurrence:
F(n) = F(n-1) + F(n-2)
n Avec les conditions initiales:
F(0) = 0, F(1) = 1
n Solutionnons cette récurrence.
n Pour cela nous devons trouver le terme général F(n)

n La méthode de substitutions à rebours est impuissante ici

n C’est un cas particulier d’une relation de récurrence linéaire homogène du

second ordre.
n Pour résoudre ce type de récurrence, nous utiliserons la méthode de
l’équation caractéristique
n (La méthode de substitutions à rebours fonction bien pour les récurrences
du premier ordre)

Mario Marchand IFT-3001, Chapitre 2 65

 Récurrences linéaires du second ordre

n Une récurrence linéaire du second ordre est une récurrence de la

forme:
a x(n) + b x(n-1) + c x(n-2) = f(n)

n où a, b et c sont des constantes réelles, indépendantes de n, et a ¹ 0.

n La récurrence est dite homogène lorsque f(n) = 0. Sinon elle est
inhomogène.
n La récurrence de Fibonacci est une récurrence homogène de cette
forme avec a = 1, b = c = -1, car elle s’écrit:
F(n) – F(n-1) – F(n-2) = 0

n Analysons alors le cas homogène:

a x(n) + b x(n-1) + c x(n-2) = 0

Mario Marchand IFT-3001, Chapitre 2 66

 Méthode de l’équation caractéristique

n Théorème: Considérez l’équation caractéristique:

a r2 + b r + c = 0
n avec les mêmes coefficients a,b,c, que ceux de relation de récurrence:
a x(n) + b x(n-1) + c x(n-2) = 0
n Désignons les deux racines de l’équation caractéristique par r1 et r2

n Si r1 ¹ r2: La solution générale de la récurrence est donnée par:

x(n) = a r1n + b r2n

n Si r1 = r2: La solution générale est donnée par:

x(n) = a r1n + b n r1n

n Dans tous les cas, a et b sont déterminés par les conditions

initiales de la récurrence, c.-à-d. par x(0) et x(1)

Mario Marchand IFT-3001, Chapitre 2 67

 Méthode de l’équation caractéristique (suite)

n Preuve du théorème: Si nous substituons x(n) = rn dans la relation de

récurrence nous obtenons:
a rn + b rn-1 + c rn-2 = 0 , (a r2 + b r + c)rn-2 = 0
, a r2 + b r + c = 0 ou r = 0 (solution triviale sans intérêt)
n Donc x(n) = rn est une solution de la récurrence lorsque r est une

racine de l’équation caractéristique

n Lorsque l’équation caractéristique possède deux racines distinctes

r1 et r2, toute combinaison linéaire x(n) = a r1n + b r2n sera
également solution de la récurrence linéaire
n Ceci est la solution la plus générale, car les deux paramètres a

et b peuvent satisfaire toute condition initiale x(0), x(1):

x(0) = a + b
x(1) = a r1 + b r2

Mario Marchand IFT-3001, Chapitre 2 68

 Méthode de l’équation caractéristique (suite)

n …suite de la preuve… Mais lorsque l’équation caractéristique

admet une seule racine distincte r1 = r2, la combinaison linéaire
devient x(n) = (a + b)r1n = g r1n et nous ne pouvons plus satisfaire
toutes les conditions initiales possibles
n Nous allons démontrer que, dans ce cas, x(n) = n r1n est une autre
solution de la récurrence. Ainsi la combinaison linéaire x(n) = a r1n
+ b n r1n nous donnera la solution générale permettant de
satisfaire toute condition initiale
x(0) = a
x(1) = a r1 + b r1
n Pour démontrer que x(n) = n r1n est une solution de la récurrence,
exploitons le fait que lorsque l’équation caractéristique possède
une seule racine r1, on a:
a r2 + b r + c = s(r – r1)2
n Pour une certaine valeur réelle s ¹ 0

Mario Marchand IFT-3001, Chapitre 2 69

 Méthode de l’équation caractéristique (suite)

n …suite de la preuve…
n Ainsi, lorsque x(n) = n rn, a x(n) + b x(n-1) + c x(n-2) devient égal à:

n Donc a x(n) + b x(n-1) + c x(n-2) = 0 lorsque x(n) = n r1n . CQFD.

n La méthode de l’équation caractéristique se généralise aux récurrences

linéaires d’ordre k, mais, dans ce cas, il faut trouver les racines d’un
polynôme d’ordre k…

Mario Marchand IFT-3001, Chapitre 2 70

 De retour à Fibonacci

n Solutionnons la récurrence de Fibonacci:

F(n) – F(n-1) – F(n-2) = 0
Avec: F(0) = 0, F(1) = 1
n L’équation caractéristique associée à cette récurrence est:
r2 – r – 1 = 0
n Les racines de cette équation sont données par:

n Puisque nous avons deux racines distinctes réelles, la solution

générale de la récurrence de Fibonacci est donnée par:

Mario Marchand IFT-3001, Chapitre 2 71

 De retour à Fibonacci (suite)

n Les valeurs de a et b sont déterminées par les conditions initiales:

n La solution de ce système est obtenue en substituant b = -a dans la

seconde équation et en isolant a. Nous trouvons alors a = 5-1/2 et
b = -5-1/2. Alors:

n F(n) augmente donc exponentiellement rapidement avec n car |y| < 1

et alors yn → 0 lorsque n → ∞.

Mario Marchand IFT-3001, Chapitre 2 72

 Algorithme récursif pour générer les nombres de Fibonacci

ALGORITHME FibRec(n) n La valeur de F(n) augmente

// Entrée: un entier n ≥ 0 exponentiellement avec n
// Sortie: le nième nombre de Fibonacci n Alors ce n’est pas vraiment réaliste
de compter chaque addition comme
If n ≤ 1 return n valant une opération élémentaire
else return FibRec(n-1)+FibRec(n-2) n Mais c’est ce que nous ferons ici
(par simplicité)
n Quel est le temps d’exécution de n Sinon, un choix valide pour
cet algorithme? l’opération de base serait
n L’opération de base est « + » l’addition de deux bits
n Le nombre C(n) de fois que cette n Le nombre d’opérations de
opération de base est effectuée ne base pour effectuer F(n-1) +
dépend que de n: F(n-2) serait alors donné par
n C(n) = Cbest(n) = Cworst(n) ⎡lg(F(n-1)+1)⎤ ∈ Q(n)
n Notez que la taille de l’instance est n Pour simplifier, supposons ici que
⎡lg(n+1)⎤ F(n-1) + F(n-2) nécessite
seulement une opération de base

Mario Marchand IFT-3001, Chapitre 2 73

 Algorithme récursif pour générer les nombres de Fibonacci (suite)

n Avec cette hypothèse simplificatrice, la valeur de C(n) est donnée par:

n C(n) = C(n-1) + C(n-2) +1

n Nous obtenons alors la relation de récurrence inhomogène:

n C(n) – C(n-1) – C(n-2) = 1

n Avec: C(0) = 0, C(1) = 0

n Théorème: La solution générale d’une récurrence linéaire

inhomogène est donnée par la somme de la solution générale à la
récurrence homogène correspondante et d’une solution particulière à
la récurrence linéaire inhomogène.
n Il est en général difficile de trouver une solution particulière de la

récurrence inhomogène.
n Mais c’est facile lorsque le terme inhomogène est une constante,

car, dans ce cas, une solution particulière constante existe!

Mario Marchand IFT-3001, Chapitre 2 74

 Algorithme récursif pour générer les nombres de Fibonacci (suite)

n Cherchons donc une solution particulière donnée par C(n) = c

n En substituant cette solution dans notre récurrence, nous trouvons
n c – c – c = 1. Alors c = -1.

n Puisque l’équation caractéristique homogène associée à notre

récurrence pour C(n) est:
n r2 – r – 1 = 0

n La solution générale de la récurrence homogène est alors donnée par:

n La solution générale de notre récurrence inhomogène pour C(n) est

alors donnée par:

Mario Marchand IFT-3001, Chapitre 2 75

 Algorithme récursif pour générer les nombres de Fibonacci (suite)

n La solution générale pour C(n) +1 = D(n) est donc identique à celle

que nous avions obtenue pour F(n).

n Les conditions initiales pour D(n) sont, en fait, celles pour F(n+1):
n D(0) = C(0) + 1 = 1 = F(1)

n D(1) = C(1) + 1 = 1 = F(2)

n On a alors que D(n) = F(n+1) ) C(n) = F(n+1) – 1

n Le nombre d’additions augmente alors exponentiellement avec n

n C’est donc une exponentielle d’exponentiel en la taille de n

n Une telle inefficacité vient du fait que chaque valeur de F(n) est
calculée plusieurs fois.

Mario Marchand IFT-3001, Chapitre 2 76

 Algorithme récursif pour générer les nombres de Fibonacci (suite)

n En effet, FibRec(5) génère l’arbre ci-dessous d’appels récursifs:

n Notez le nombre d’appels F(1) généré par FibRec(5)

n La concision d’un algorithme récursif n’est pas garante de son efficacité.

n Ici c’est particulièrement médiocre!

Mario Marchand IFT-3001, Chapitre 2 77

 Algorithme non récursif pour générer les nombres de Fibonacci

ALGORITHME FibNonRec(n)
// Entrée: un entier n ≥ 0
// Sortie: le nième nombre de Fibonacci

If n=0 return 0
u ← 0; v ← 1
for i ← 2 to n do
v←v+u
u←v–u
return v

n Si v+u est notre opération de base, nous avons C(n) = n – 1 (∀ n > 0)

n Cet algorithme ne nécessite que Q(n) additions.
n FibNonRec(n) est donc nettement plus efficace que FibRec(n)

Mario Marchand IFT-3001, Chapitre 2 78

 Lecture (Levitin)

n Chapitre 2
n 2.1 The Analysis Framework

n 2.2 Asymptotic Notations and Basic Efficiency Classes

n 2.3 Mathematical Analysis of Nonrecursive Algorithms

n 2.4 Mathematical Analysis of Recursive Algorithms

Mario Marchand IFT-3001, Chapitre 2 79