¿Dadas $n! = c$, cómo encontrar $n$?

Question

Estoy lidiando con un problema de complejidad de tiempo en el que sé que el tiempo en marcha de un algoritmo:

$$t = 1000 \mathrm{ms} .$$

También sé que el algoritmo es superior delimitada por $O(n!)$.

Quiero saber el tamaño aproximado de la entrada $n$ en base a esto:

$$ f(n) = n! = t $$ $$ f^{-1}(t) = n = ? $$

Answer 1

Usted puede utilizar Stirling' fórmula de aproximación:

$$\log n! = n\log n - n + \log (2\pi n)/2 + \mathcal{O}(1/n)$$

Así que usted puede tomar la aproximación como

$$\log n! \approx n\log n - n + \log (2\pi n)/2 $$

% Ahora dado $n! = c$, usted puede calcular un valor aproximado para $n$ al hacer una búsqueda binaria simple en la fórmula anterior.

Si desea una fórmula directa para calcular y el valor aproximado para $n$, Shai Covo ha dado un enlace a un hilo de mathoverflow.

Answer 2

También depende del algoritmo. Usted necesita un algoritmo que se puede traducir a un "ajeno TM", una Máquina de Turing, donde los movimientos de la cabeza depende sólo del tiempo de paso estamos actualmente. Si el algoritmo de tiempo de ejecución es diferente para diferentes entradas del mismo tamaño, es que si se utiliza loops que puede ser terminado abruptamente (como cuando realizamos la búsqueda de una o más ocurrencias de un elemento) o condicionales que cada caso tiene diferentes tiempos de ejecución (por ejemplo, algunas heurísticas), yo creo que aproximar el tamaño de entrada es aún más difícil.

Sin embargo, estoy curioso acerca de su motivo. ¿Por qué no el tamaño de entrada se conoce de antemano?