Livre_silo 30 août 2013 16:32 Page 138
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
138
Informatique pour tous
5.3.3 Complexité d’une fonction récursive
On explique ici comment calculer le coût d’une fonction récursive, à savoir le nombre
d’opérations élémentaires qu’ elle effectue ou son occupation mémoire totale. La notion
de complexité sera présentée plus en détail dans le prochain chapitre, section 6.1.
Reprenons l’exemple de la fonction u (définie p. 130) :
def u(n):
if n == 0:
return 2.
else:
x = u(n-1)
return 0.5 * (x + 3. / x)
et évaluons le nombre d’opérations arithmétiques (addition, multiplication et division)
qu’elle effectue.
Si n désigne la valeur de son argument, notons C(n) ce nombre d’opérations. En suivant
la définition de la fonction u, on obtient les deux équations suivantes :
C(0) = 0
C(n) = C(n − 1) + 3
En effet, dans le cas n = 0, on ne fait aucune opération arithmétique. Et dans le cas n > 0,
on fait d’une part un appel récursif sur la valeur n − 1, d’où C(n − 1) opérations, puis trois
opérations arithmétiques (une multiplication, une addition et une division). Il s’agit d’une
suite arithmétique de raison 3, dont le terme général est :
C(n) = 3n
Le nombre d’opérations arithmétiques effectuées par la fonction u est donc proportionnel
à n.
Si en revanche on avait écrit la fonction u plus naïvement, avec deux appels récursifs u(n-1),
c’est-à-dire :
def u(n):
if n == 0:
return 2.
else:
return 0.5 * (u(n-1) + 3. / u(n-1))
alors les équations définissant C(n) seraient les suivantes :
C(0) = 0
C(n) = C(n − 1) + C(n − 1) + 3
En effet, il convient de prendre en compte le coût C(n − 1) des deux appels à u(n-1). Il
s’agit maintenant d’une suite arithmético-géométrique, dont le terme général est :
C(n) = 3(2
n
− 1)
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
138
Informatique pour tous
5.3.3 Complexité d’une fonction récursive
On explique ici comment calculer le coût d’une fonction récursive, à savoir le nombre
d’opérations élémentaires qu’ elle effectue ou son occupation mémoire totale. La notion
de complexité sera présentée plus en détail dans le prochain chapitre, section 6.1.
Reprenons l’exemple de la fonction u (définie p. 130) :
def u(n):
if n == 0:
return 2.
else:
x = u(n-1)
return 0.5 * (x + 3. / x)
et évaluons le nombre d’opérations arithmétiques (addition, multiplication et division)
qu’elle effectue.
Si n désigne la valeur de son argument, notons C(n) ce nombre d’opérations. En suivant
la définition de la fonction u, on obtient les deux équations suivantes :
C(0) = 0
C(n) = C(n − 1) + 3
En effet, dans le cas n = 0, on ne fait aucune opération arithmétique. Et dans le cas n > 0,
on fait d’une part un appel récursif sur la valeur n − 1, d’où C(n − 1) opérations, puis trois
opérations arithmétiques (une multiplication, une addition et une division). Il s’agit d’une
suite arithmétique de raison 3, dont le terme général est :
C(n) = 3n
Le nombre d’opérations arithmétiques effectuées par la fonction u est donc proportionnel
à n.
Si en revanche on avait écrit la fonction u plus naïvement, avec deux appels récursifs u(n-1),
c’est-à-dire :
def u(n):
if n == 0:
return 2.
else:
return 0.5 * (u(n-1) + 3. / u(n-1))
alors les équations définissant C(n) seraient les suivantes :
C(0) = 0
C(n) = C(n − 1) + C(n − 1) + 3
En effet, il convient de prendre en compte le coût C(n − 1) des deux appels à u(n-1). Il
s’agit maintenant d’une suite arithmético-géométrique, dont le terme général est :
C(n) = 3(2
n
− 1)