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

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