二项式系数函数的增长是阶乘还是多项式？

Question

我编写了一个算法，给定一个单词列表，必须检查该单词列表中每个唯一的四个单词组合（无论顺序如何）。

要检查的组合数 x 可以使用二项式系数计算，即 x = n!/(r!(n-r)!)，其中 n 是列表中单词的总数，而 r 是每个组合中单词的数量，在我的情况下始终为4，因此函数是 x = n!/(4!(n-4)!) = n!/(24(n-4)!)。因此，随着总单词数 n 的增加，要检查的组合数 x 增长得阶乘级别，对吗？

让我感到困惑的是，WolframAlpha能够将这个函数重写为 x = (n^4)/24 − (n^3)/4 + (11.n^2)/24 − n/4，因此现在似乎随着 n 的增长，它的增长变得多项式级别了？那么到底是哪种情况呢？！

这里有一个图表来说明函数的增长情况（将字母 x 替换为 l）

- Tyler Bevan

Answer 1

对于固定的r值，该函数为O(n^r)。在您的情况下，r = 4，它是O(n^4)。这是因为分子中的大多数项被分母抵消了：

n!/(4!(n-4)!) 
   = n(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)...(3)(2)(1) 
     -------------------------------------------
     4!(n-4)(n-5)(n-6)...(3)(2)(1)

   = n(n-1)(n-2)(n-3)
     ----------------
           4!

这是一个关于n的4次多项式。

- Jeremy West