No creo que haya una manera de encontrar el factorial de un número en el tiempo O (log n). (Excepto la aproximación_de Stirling, no precisa).
Sin embargo, en caso de que necesite encontrar factorial de muchos números una y otra vez, no necesita gastar O (n) tiempo para cada uno. Puedes hacerlo todo en O (n).
Usando la programación dinámica !!!
Considere un conjunto de datos de 10 ^ 5 elementos con cada elemento alcanzando un valor máximo de 10 ^ 5.
- En el peor de los casos, el tiempo máximo que tarda su algoritmo será 10 ^ 5 * 10 ^ 5 (10 ^ 5 para calcular el factorial de cada elemento * 10 ^ 5 elementos)
PERO, si guardamos los resultados calculados previamente en una matriz, podemos reducir esta complejidad de a a O (n).
- ¿Cuál es la forma más rápida de encontrar el número original antes del descuento a mano? (números grandes)
- ¿Alguien puede ayudarme a resolver el problema SPOJ "Consulta en un árbol" (QTREE)?
- ¿Cuál es la relación entre el índice de una matriz y el tamaño de una matriz?
- ¿Cuál es la última actualización del algoritmo SEO de Google en 2017?
- ¿Cuál es la relación entre matrices y matrices variables de programas de computadora?
Lea estas líneas de código cuidadosamente
hecho largo largo [N + 1];
hecho [0] = 1;
para (int i = 1; i <= N; ++ i)
hecho [i] = hecho [i-1] * i;
aquí N = valor del elemento máximo fuera del conjunto de datos
Este código simplifica la búsqueda de factorial.
La matriz de hechos ahora tiene factorial de 10 ^ 5 elementos en solo 10 ^ 5 tiempo.
- Entonces, incluso en el peor de los casos, el tiempo máximo que tomará este algoritmo será 10 ^ 5 + 10 ^ 5 (10 ^ 5 para calcular previamente el factorial de todos los elementos y O (1) para obtener el factorial)
Cambiando * a +
Espero que haya ayudado !!
