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

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 的增长而 多项式 增长？那是哪一个？！

Here is a graph to visualise the growth of the function (the letter x is switched to an l)

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 次多项式。

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

Is the growth of the binomial coefficient function factorial or polynomial

big-o

time-complexity

binomial-coefficients