M！/ n的复杂性分析！（m-n）！

Question

给出了算法的运行时间为m！/（n！*（m-n）！），即m和n是变量，是复杂性因子或多项式吗？或者是别的吗？

请详细说明。

感谢

Answer 1

增长可以是线性的或常量，具体取决于 $ m $ 和 $ n $ 随着他们的成长。例如，如果 $ n $ 生长为 $ m $ ，如 $ m= n + 1 $ ，然后 $ \ binom {m} {n}=binom {n + 1} {n}= n + 1 $ 。

现在，如果您对最大增长感兴趣，那么二项式系数 $ \ binom {m} {n} $ 当 $ n $ 是 $ m $ 的一半。 put $ 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} $$