评估二项式系数的时间复杂度

Question

我是理论计算机科学的新手，我想计算以下算法的时间复杂度，该算法评估定义为

的二项式系数

nf = 1; 
for i = 2 to n do nf = nf * i; 
kf = 1; 
for i = 2 to k do kf = kf * i; 
nkf = 1; 
for i = 2 to n-k do nkf = nkf * i; 
c = nf / (kf * nkf);

我的教科书建议使用斯特林近似

但是，考虑到 for i = 2 to n do nf = nf * i; 的复杂度为 O(n-2)=O(n)，这是主要的，我可以得到相同的结果。

斯特林的近似值似乎有点矫枉过正。我的方法错了吗？

Answer 1

在您的第一种方法中，您计算了 n!, k!和（n-k）！分别计算二项式系数。因此，由于所有这些项最多可以用 O(n) 时间复杂度的操作来计算。

但是，你对计算斯特林公式的时间复杂度是错误的。您只需要在以 2 为基数的操作中使用 log(n) 来计算它。这是因为当尝试计算某个实数的 p 次方时，您可以不乘以它 p 次，而是继续对数字进行平方以快速计算它。例如：

如果你想计算 2^17，而不是像这样进行 17 次操作：

return 2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2*2

你可以这样做：

a = 2*2
b = a*a
c = b*b
d = c*c
return d * 2

只有5次操作。

注意：但是请记住，斯特林公式不等于阶乘。这只是一个近似值，但却是一个很好的近似值。

编辑：也可以把a^n看成e^(log(a)*n)然后用快速收敛级数展开计算

1 + (log(a)n) + ((log(a)n)^2)/2！ + ((log(a)n)^3)/3! + ...

由于级数收敛得非常快，您可以立即获得非常接近的近似值。

Evaluating time complexity for the binomial coefficient