m! / n! (M-N)의 복잡성 분석!

Question

알고리즘의 런타임이 M과 n이 모두 변수 인 MCN이되는 MCN이되는 MCN이되는 MCN은 복잡성 계승 또는 다항식입니까?아니면 다른 것입니까?

제발 정교하십시오.

감사합니다

Answer 1

$ M $ 및 $ n $ 사이의 관계에 따라 성장이 선형이거나 일정 할 수 있습니다. 그들이 크게 자라면서. 예를 들어 $ n $ 이 $ m $ 에서 $ m= n + 1 $ , $ \ binom {m} {n}= binom {n + 1} {n}= n + 1 $ .

이제는 최대 성장에 관심이 있으시면 이항 계수 $ \ binom {m} {SPAN CLASS="일 때 가장 크다. 수학 용기 "> $ n $ 은 $ m $ 의 절반입니다. $ m= 2N $ 을 넣고 계승을 위해 소박한 근사치 .

를 얻습니다

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