Сложность scipy.special.binom?

Question

Согласно этому ответу , есть две функции для вычисления биномиального коэффициента, также известные как «N выбирают K». Одним из них является scipy.special.binom().

Где реализована эта функция? Все, что я знаю, это то, что это уфун c.

Кроме того, какова временная сложность scipy.special.binom()?

Answer 1

Источник можно найти на Github в orthogonal_eval.pxd .

В целочисленном случае сложность 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