La clé ici est de visualiser l'arbre d'appel. Une fois cela fait, la complexité est :
nodes of the call tree * complexity of other code in the function
le dernier terme peut être calculé de la même manière que pour une fonction itérative normale.
Au lieu de cela, le nombre total de nœuds d'un arbre complet est calculé comme suit
C^L - 1
------- , when C>1
/ C - 1
/
# of nodes =
\
\
L , when C=1 (this is special case of a single branch tree)
Où C est le nombre d'enfants de chaque nœud et L est le nombre de niveaux de l'arbre (racine comprise).
Il est facile de visualiser l'arbre. Partez du premier appel (nœud racine) puis dessinez un nombre d'enfants égal au nombre d'appels récursifs de la fonction. Il est également utile d'écrire le paramètre passé à la sous-appel comme "valeur du noeud".
Voici donc les résultats pour les exemples ci-dessus :
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
Pensez d'abord à l'arbre d'appel :
n level 1
n-1 level 2
n-2 level 3
n-3 level 4
... ~ n levels -> L = n
Ici, le nombre d'enfants par nœud est C = 1, et le nombre de niveaux L = n+1. La complexité du reste de la fonction est O(1). Par conséquent, la complexité totale est L * O(1) = (n+1) * O(1) = (n+1) * O(1). O(n)
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
L'arbre d'appel est ici :
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
De nouveau C = 1, mais L = n/5. La complexité du reste de la fonction est O(1). Par conséquent, la complexité totale est L * O(1) = (n/5) * O(1) = (n/5) * O(1). O(n)
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
L'arbre d'appel est :
n
n/5
n/5^2
n/5^3
... ~ log5(n) levels -> L = log5(n)
Donc C = 1, L = log(n). La complexité du reste de la fonction est O(1). Donc la complexité totale est L * O(1) = log5(n) * O(1) = O(log(n))
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
Ici, l'arbre d'appel est plus complexe :
n level 1
n-1 n-1 level 2
n-2 n-2 n-2 n-2 ...
n-3 n-3 n-3 n-3 n-3 n-3 n-3 n-3 ...
... ~ n levels -> L = n
Ici, le nombre d'enfants par nœud est C = 2, tandis que L = n. La complexité du reste de la fonction est O(1). Cette fois, nous utilisons la formule complète pour le nombre de noeuds dans l'arbre d'appel car C > 1. Par conséquent, la complexité totale est de (C^L-1)/(C-1) * O(1) = (2^n - 1) * O(1) = (2^n - 1) * O(1) O(2^n) .
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
Encore une fois, l'arbre d'appel est :
n
n-5
n-10
n-15
... ~ n/5 levels -> L = n/5
Ici C = 1, L = n/5. La complexité du reste de la fonction est O(n). Donc la complexité totale est L * O(1) = (n/5) * O(n) = O(n^2)
