是二项式系数函数的增长因子或多项式

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）

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