•  21-09-2019
  •  | 
  •  

Question

Pourquoi la relation de récurrence de l'algorithme récursif factoriel cela? 

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

Pourquoi est-ce pas? 

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

Mise valeurs de n i.e. 1,2,3,4 ...... la seconde relation de récurrence cales (factorielles sont correctement calculés) pas la première.

Était-ce utile?

La solution

Cette question est très déroutant ... Vous avez d'abord la formule n'est pas factoriel. Il est tout simplement T (n) = n + 1, pour tout n. Factorielle de n est le produit des entiers positifs n premières: factoriel (1) = 1. factoriel (n) = n * factorielle (n-1). Votre deuxième formule est essentiellement correcte.

Autres conseils

On dirait T (n) est la relation de récurrence du Complexité de l'algorithme factoriel récursive, en supposant la multiplication de temps constant. Peut-être vous avez mal lu source?

nous utilisons généralement relation de récurrence pour trouver la complexité temporelle de l'algorithme.

Ici, la fonction T (n) est pas vraiment pour le calcul de la valeur d'un factoriel, mais il vous dit au sujet de la complexité temporelle de l'algorithme factoriel.

Cela signifie pour trouver un factoriel de n il faudra 1 fonctionnement plus que factoriel de n-1 (À savoir T (n) = T (n-1) 1) et ainsi de suite.

relation correcte de récurrence pour un algorithme récursif est factoriel T (n) = 1 pour n = 0 T (n) = 1 + T (n-1) pour n> 0 pas que vous avez mentionné plus tard.

comme récurrence pour tour de hanoi est T (n) = 2T (n-1) 1 pour n> 0;

Je suppose que vous avez de mauvaises informations. La seconde relation de récurrence vous citez est le bon, comme vous l'avez observé. Le premier produit juste les nombres naturels.

Où avez-vous trouvé le premier? Il est complètement faux.

Il va seulement ajouter 1 à chaque fois que quelle que soit la valeur.

Ce qu'il n'a pas été mis à la récursion factoriel, mais la complexité du temps de celui-ci.
À supposer que c'est le pseudo-code pour une telle récurrence: 

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • Je suppose que l'élimination récursivité queue ne participe pas.

Ligne 2 et 3 coûts une constante de temps, c1 et c2.
Ligne 4 coûte une constante de temps ainsi. Cependant, il appelle factoriel (n-1), qui prendra un certain temps T (n-1). En outre, le temps nécessaire pour multiplier factoriel (n-1) par n peut être ignoré une fois T (n-1) est utilisé.
Le temps pour toute la fonction est simplement la somme:. T (n) = C1 + C2 + T (n-1)
Ceci, en notation grand-o, est réduite à T (n) = 1 + T (n-1).

Ceci est, comme Diam l'a souligné, est un récursion plat, donc son temps d'exécution doit être O (n). Sa complexité spatiale sera énorme si.

T (n) = T (n-1) + 1 est l'équation de récurrence correcte pour factorielle de n. Cette équation vous donne le temps de calculer factoriel de n pas valeur du factoriel de n.

D'abord, vous devez trouver une opération de base et cet exemple est la multiplication. Se produit une fois dans la multiplication chaque récursion. Alors T (n) = T (n-1) +1 ce +1 est le fonctionnement de base (mutliplication pour cet exemple) T (n-1) est prochain appel récursif.

TL; DR: La réponse à votre question dépend en fait de quelle séquence votre relation de récurrence est définir . Autrement dit, si la séquence T n dans votre question représente la fonction factoriel ou le coût du temps de fonctionnement du calcul de la fonction factoriel X .

La fonction factoriel

récursif defintion de la factorielle de n , f n , est la suivante:

f n = n • f n-1 pour n> 0 avec f < sub> 0 = 1 .

Comme vous pouvez le voir, l'équation est au-dessus en fait un relation de récurrence , car il est un équation qui, en même temps que la durée initiale (par exemple, f 0 = 1 ) récursivement définit une séquence (par exemple, la fonction factorielle, f n ).

Modélisation du coût du temps de fonctionnement du calcul du factoriel

Maintenant, nous allons trouver un modèle pour représenter le coût du temps de fonctionnement du calcul du factoriel de n . Appelons T n coût durée de calcul f n .

En regardant la définition ci-dessus de la fonction factoriel f n , son coût en temps de course T n comprendra le coût du temps de fonctionnement du calcul f n-1 (à savoir, ce coût est T n-1 ) ainsi que le coût du temps de fonctionnement de la multiplication entre l'exécution n et f n-1 . La multiplication est réalisée en temps constant. Par conséquent, nous pourrions dire que T n = T n-1 + 1 .

Cependant, quelle est la valeur de T 0 ? T 0 représente le coût en temps de calcul en cours d'exécution f 0 . Étant donné que la valeur de f 0 est d'abord connu par définition, le coût du temps de fonctionnement pour calculer f 0 en fait constante. Par conséquent, on pourrait dire que T 0 = 1 .

Enfin, ce que nous obtenons est:

T n = T n-1 + 1 pour n> 0 avec T < sub> 0 = 1 .

Cette équation ci-dessus est également une relation de récurrence . Cependant, ce qu'il définit (en même temps que la durée initiale), est une séquence qui modèles coût en temps de fonctionnement du calcul de la fonction factoriel .

X Compte tenu de la façon dont la séquence dans votre relation de récurrence est appelée (c.-à- T n ), je pense qu'il très probablement celui-ci représente, par exemple, le coût du temps de fonctionnement du calcul de la fonction factoriel .

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top