Análisis de complejidad de M! / N! (M-N)!

Question

Dado el tiempo de ejecución de un algoritmo para ser m! / (n! * (m-n)!) Que es MCN, donde tanto M como N son variables, ¿es la complejidad factorial o polinomial?¿O es algo más?

por favor elaborado.

gracias

Answer 1

Los crecimientos podrían ser lineales o constantes, dependiendo de la relación entre $ m $ y $ n $ A medida que crecen. Por ejemplo, si $ n $ crece con $ m $ como en $ m= n + 1 $ , luego $ \ binom {m} {n}=binom {n + 1} {n}= N + 1 $ .

Ahora, si está interesado en el crecimiento máximo, entonces los coeficientes binomiales $ \ binom {m} {n} $ son más grandes cuando $ n $ es la mitad de $ m $ . Ponga $ m= 2n $ y use Aproximación de Stirling para el factorial. Obtienes

$$ \ binom {2n} {n}=frac {(2n)!} {(n!) ^ 2} \ sim \ frac {(2n) ^ { 2n} e ^ {- 2n} \ sqrt {4n \ pi}} {n ^ {2n} e ^ {- 2n} 2n \ pi}=pi ^ {- 1/2} 2 ^ {2N} N ^ { -1/2} $$