Analyse de la complexité de M! / N! (M-N)!

Question

Compte tenu du temps d'exécution d'un algorithme pour être M! / (n! * (m-n)!) C'est MCN, où les variables m et n sont-elles à la fois la complexité factorielle ou polynomial?Ou est-ce quelque chose d'autre?

S'il vous plaît élaborer.

merci

Answer 1

Les excroissances peuvent être linéaires ou constantes en fonction de la relation entre $ M $ et $ n $ comme ils grandissent gros. Par exemple, si $ n $ augmente avec $ m $ comme dans $ m= n + 1 $ , puis $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ .

Maintenant, si vous êtes intéressé par la croissance maximale, les coefficients binomiaux $ \ binom {m} {n} $ sont les plus grands quand $ N $ est la moitié de $ M $ . Mettre $ m= 2n $ et utiliser Approximation de Stirling pour la factorielle. Vous obtenez

$$ \ 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} $$