Discussion :

[sisiniya]

Bonjour,

J'aimerai bien savoir votre avis sur la complexité de cette fonction récursive suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
int fct(int n)
{
   if(n < 0) return 1;
   else
        return (fct(n-1) - fct(n-1));
}

Mercii pour votre aide.

Sisiniya.

[Pouet_forever]

Pour la complexité je dirais en 0(N!)
Maintenant quand à ton code je ne vois pas trop son intérêt, il renverra toujours 0
Tu calcules fct de n-1 et tu le soustrait à fct de n-1 du coup f(n-1) - f(n-1) = 0

[sisiniya]

Oui il renvoi 0 pour des nombres positives c'est ça. Juste c'est un exemple pour calculer la complexité de ce type de fonction récursive.

En fait, pourquoi vous avez dit O(n!), moi je vois que c'est O(n) . Que dites - vous ?

Merci.

Sisiniya

[Lavock]

O(2^n) . Plus précisément, (2)^(n+1)-1

Tu appelle deux fois ta fonction en n-1. Donc à chaque étape, tu double ton nombre de fonction appelé ! Et c'est pas parce-que c'est la même fonction qu'elle n'est pas renouvelé entièrement.

n=0, 1
n=1, 3 = 2*1 +1
n=2, 7 = (2*1 + 1)*2+1
etc...