scipy.special.binom 的复杂度？

Question

根据this answer, there are two functions to calculate the binomial coefficient, also known as "N choose K". One of them is scipy.special.binom()。

这个功能是在哪里实现的？我只知道它是 ufunc.

另外，scipy.special.binom()的时间复杂度是多少？

Answer 1

可以在 orthogonal_eval.pxd 中的 Github 上找到源代码。

在整数情况下，复杂度为O(k)。

kx = floor(k)
if k == kx and (fabs(n) > 1e-8 or n == 0):
    # Integer case: use multiplication formula for less rounding error
    # for cases where the result is an integer.
    #
    # This cannot be used for small nonzero n due to loss of
    # precision.

    nx = floor(n)
    if nx == n and kx > nx/2 and nx > 0:
        # Reduce kx by symmetry
        kx = nx - kx

    if kx >= 0 and kx < 20:
        num = 1.0
        den = 1.0
        for i in range(1, 1 + <int>kx):
            num *= i + n - kx
            den *= i
            if fabs(num) > 1e50:
                num /= den
                den = 1.0
        return num/den

scipy.special.binom 的复杂度？

Complexity of scipy.special.binom?

scipy

binomial-coefficients