Análise de complexidade de m! / N! (M-N)!

Question

Dado o tempo de execução de um algoritmo para ser m! / (n! * (M-n)!) que é MCN, onde ambos os e n são variáveis, é o fatorial ou polinômio de complexidade?Ou é outra coisa?

por favor elabore.

obrigado

Answer 1

Os crescimentos podem ser lineares ou constantes, dependendo da relação entre $ m $ e $ n $ como eles crescem grandes. Por exemplo, se $ n $ cresce com $ m $ como no recipiente de matemática $ m= n + 1 $ , então $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ .

Agora, se você estiver interessado no crescimento máximo, então os coeficientes binomiais $ \ binom {m} {n} $ são maiores quando $ n $ é metade da $ m $ . Coloque $ m= 2n $ e use Aproximação de Stirling para o fatorial. Você ganha

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