complexity-theory - recursividad - torres de hanoi algoritmo recursivo

Complejidad del programa factorial recursivo.

Question

¿Cuál es la complejidad de un programa recursivo para encontrar factorial de un número n ? Mi corazonada es que podría ser O(n) .

Answer 1

Cuando expresas la complejidad de un algoritmo, siempre es como una función del tamaño de entrada. Solo es válido suponer que la multiplicación es una operación O(1) si los números que está multiplicando son de tamaño fijo. Por ejemplo, si desea determinar la complejidad de un algoritmo que calcula productos de matriz, puede suponer que los componentes individuales de las matrices eran de tamaño fijo. Entonces sería válido suponer que la multiplicación de dos componentes de la matriz individual fue O(1) , y calcularía la complejidad de acuerdo con el número de entradas en cada matriz.

Sin embargo, cuando desee descubrir la complejidad de un algoritmo para calcular N! debe asumir que N puede ser arbitrariamente grande, por lo que no es válido suponer que la multiplicación es una operación O(1) .

Si desea multiplicar un número de n bits con un número de m bits, el algoritmo ingenuo (el tipo que hace a mano) toma tiempo O(mn) , pero hay algoritmos más rápidos.

Si desea analizar la complejidad del algoritmo fácil para calcular N!

 factorial(N)
f=1
for i = 2 to N
f=f*i
return f

luego, en el paso k-th en el bucle for, estás multiplicando (k-1)! por k . El número de bits utilizados para representar (k-1)! es O(k log k) y el número de bits utilizados para representar k es O(log k) . ¡Así que el tiempo requerido para multiplicar (k-1)! y k es O(k (log k)^2) (suponiendo que utilice el algoritmo de multiplicación ingenua). Luego, la cantidad total de tiempo que toma el algoritmo es la suma del tiempo que se toma en cada paso:

sum k = 1 to N [k (log k)^2] <= (log N)^2 * (sum k = 1 to N [k]) =
O(N^2 (log N)^2)

Podría mejorar este rendimiento utilizando un algoritmo de multiplicación más rápido, como Schönhage-Strassen, que lleva tiempo O(n*log(n)*log(log(n))) para números de 2 n bits.

La otra forma de mejorar el rendimiento es usar un mejor algoritmo para calcular N! . ¡El más rápido que conozco primero calcula la factorización prima de N! y luego multiplica todos los factores primos.

Answer 2

La complejidad temporal del factorial recursivo sería:

factorial (n) {
if (n = 0)
return 1
else
return n * factorial(n-1)
}

Asi que,

La complejidad del tiempo para una llamada recursiva sería:

T(n) = T(n-1) + 3 (3 is for As we have to do three constant operations like
multiplication,subtraction and checking the value of n in each recursive
call)
= T(n-2) + 6 (Second recursive call)
= T(n-3) + 9 (Third recursive call)
.
.
.
.
= T(n-k) + 3k
till, k = n
Then,
= T(n-n) + 3n
= T(0) + 3n
= 1 + 3n

Para representar en notación Big-Oh,

T (N) es directamente proporcional a n,

Por lo tanto, la complejidad temporal del factorial recursivo es O (n). Como no hay espacio extra ocupado durante las llamadas recursivas, la complejidad del espacio es O (N).

Answer 3

Si toma la multiplicación como O(1) , entonces sí, O(N) es correcta. Sin embargo, tenga en cuenta que multiplicar dos números de longitud arbitraria x no es O(1) en el hardware finito, ya que x tiende a infinito, el tiempo necesario para la multiplicación aumenta (por ejemplo, si usa la multiplicación de Karatsuba , es O(x ** 1.585) ).

Teóricamente puedes hacerlo mejor con números suficientemente grandes con Schönhage-Strassen , pero confieso que no tengo experiencia en el mundo real con eso. x , la "longitud" o el "número de dígitos" (en cualquier base, no importa para big-O de todos modos, N crece con O(log N) , por supuesto.

Si pretende limitar su pregunta a factoriales de números lo suficientemente cortos como para multiplicarse en O(1) , entonces no hay forma de que N pueda "tender al infinito" y, por lo tanto, la notación de gran O es inapropiada.

Answer 4

Suponiendo que se trata del algoritmo factorial más ingenuo de todos los tiempos:

factorial (n):
if (n = 0) then return 1
otherwise return n * factorial(n-1)

Sí, el algoritmo es lineal y se ejecuta en tiempo O (n). Este es el caso porque se ejecuta una vez cada vez que disminuye el valor n , y disminuye el valor n hasta que llega a 0 , lo que significa que la función se llama recursivamente n veces. Esto supone, por supuesto, que tanto la disminución como la multiplicación son operaciones constantes.

Por supuesto, si implementa factorial de alguna otra manera (por ejemplo, usando la suma recursivamente en lugar de la multiplicación), puede terminar con un algoritmo mucho más complejo de tiempo. Sin embargo, no recomendaría el uso de tal algoritmo.