•  21-09-2019
  •  | 
  •  

Pregunta

¿Por qué es la relación de recurrencia del algoritmo recursivo factorial esto? 

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

Por qué no es esto? 

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

valores puesta de n es decir 1,2,3,4 ...... la segunda relación de recurrencia sostiene (los factoriales se calculan correctamente) no el primero.

¿Fue útil?

Solución

Esta pregunta es muy confuso ... En primer lugar, la fórmula no es factorial. Se trata simplemente de T (n) = n + 1, para todos los n. Factorial de n es el producto de los primeros n enteros positivos: factorial (1) = 1. factorial (n) = n * factorial (n-1). Su segunda fórmula es esencialmente correcta.

Otros consejos

Parece que T (n) es la relación de recurrencia de la complejidad de tiempo del algoritmo factorial recursiva, suponiendo multiplicación constante de tiempo. Tal vez leído mal su fuente?

generalmente utilizamos relación de recurrencia encontrar la complejidad del algoritmo de tiempo.

A continuación, la función T (n) no es en realidad para calcular el valor de un factorial pero le está diciendo acerca de la complejidad temporal del algoritmo factorial.

Esto significa que para encontrar un factorial de n se tardará más de 1 operación de factorial de n-1 (Es decir, T (n) = T (n-1) 1) y así sucesivamente.

relación de recurrencia de manera correcta para un algoritmo recursivo es factorial T (n) = 1 para n = 0 T (n) = 1 + T (n-1) para n> 0 No es que usted ha mencionado más adelante.

como la recurrencia de Torre de Hanoi es T (n) = 2T (n-1) 1 para n> 0;

I se supone que tiene la mala información. La segunda relación de recurrencia usted cita es la correcta, como se ha observado. El primero de ellos simplemente genera los números naturales.

¿Dónde encontró el primero? Es totalmente erróneo.

Sólo va a añadir al menos 1 cada vez que cualquiera que sea el valor es.

Lo que puso no era la recursividad factorial, pero la complejidad del tiempo de la misma.
Asumiendo que este es el pseudocódigo para una recurrencia tales: 

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • Estoy asumiendo que la eliminación de la cola-recursividad no está involucrado.

Línea 2 y 3 cuesta un tiempo constante, C1 y C2.
Línea 4 cuesta una constante de tiempo también. Sin embargo, llama factorial (n-1), que tendrá un tiempo T (n-1). Además, el tiempo que se necesita para multiplicar factorial (n-1) por n puede ser ignorada una vez T (n-1) se utiliza.
Tiempo para toda la función es simplemente la suma:. T (n) = c1 + c2 + T (n-1)
Esto, en gran-o notación, se reduce a T (n) = 1 + T (n-1).

Esto es, como Diam ha señalado, es una recursión plana, por lo tanto, su tiempo de ejecución debe ser O (n). Su complejidad espacio será enorme, aunque.

T (n) = T (n-1) + 1 es la ecuación de recurrencia correcta para factorial de n. Esta ecuación se da el tiempo para calcular factorial de n NO valor del factorial de n.

En primer lugar usted tiene que encontrar una operación de base y para este ejemplo, es la multiplicación. Multiplicación se hace una vez en cada recursividad. Entonces T (n) = T (n-1) 1 este 1 es el funcionamiento básico (mutliplication para este ejemplo) T (n-1) es llamada siguiente recursión.

TL; DR: La respuesta a su pregunta en realidad depende de qué secuencia de su relación de recurrencia es definir . Es decir, si la secuencia T n en su pregunta representa la función factorial o el costo del tiempo de tránsito de calcular la función factorial X .

La función factorial

La recursiva Defintion del factorial de n , f n , es:

f n = n • f n-1 para n> 0 con f < sub> 0 = 1 .

Como se puede ver, la ecuación anterior es en realidad un recurrencia relación , ya que es un ecuación que, junto con el término inicial (es decir, f 0 = 1 ), recursivamente define un secuencia (es decir, la función factorial, f n ).

Modelar el costo del tiempo de tránsito de calcular el factorial

Ahora, vamos a encontrar un modelo para representar el costo del tiempo de tránsito de calcular el factorial de n . Vamos a llamar a T n coste-tiempo de funcionamiento de calcular f n .

En cuanto a la definición anterior de la función factorial f n , su coste de tiempo de marcha T n consistirá en el coste de tiempo de marcha de calcular f n-1 (es decir, este costo es T n-1 ) más el coste de tiempo de marcha de la realización de la multiplicación entre n y f n-1 . La multiplicación se logra en un tiempo constante. Por lo tanto, podríamos decir que T n = T n-1 + 1 .

Sin embargo, ¿cuál es el valor de T 0 ? T 0 representa el coste de tiempo de marcha de calcular f 0 . Como el valor de f 0 se conoce inicialmente por definición, el coste de tiempo de marcha para calcular f 0 es En realidad constante. Por lo tanto, podríamos decir que T 0 = 1 .

Por último, lo que obtenemos es:

T n = T n-1 + 1 para n> 0 con T < sub> 0 = 1 .

Esta ecuación anterior es también un relación de recurrencia . Sin embargo, lo que define (junto con el término inicial), es una secuencia que modelos el coste de tiempo de marcha de calcular la función factorial .

X Teniendo en cuenta la forma en la secuencia en su relación de recurrencia se llama (es decir, T n ), creo que muy probable representa el último, es decir, el coste de tiempo de marcha de calcular la función factorial .

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top