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

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