Анализ сложности M! / N! (M-N)!

Question

Учитывая время выполнения алгоритма m! / (n! * (m-n)!) То есть MCN, где как M и N являются переменными, является факториалом сложности или многочлен?Или это что-то еще?

Пожалуйста, сложите.

Спасибо

Answer 1

Рост может быть линейным или постоянным в зависимости от взаимосвязи между $ m $ и $ n $ как они растут. Например, если $ n $ растет с $ m $ как в $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ .

Теперь, если вы заинтересованы в максимальном росте, то биномиальные коэффициенты $ \ binom {m} {n} $ крупнейшие, когда $ n $ - это половина $ m $ . Поместите $ m= 2n $ и используйте Приближение Стирлинга для факториала. Вы получаете

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