Какова временная сложность `math.comb ()` в Python 3.8?

Question

https://docs.python.org/3/library/math.html#math .comb

Это удобная и удобная функция для решения n выбор k задач без необходимости сборки с нуля. Кто-нибудь знает временную сложность этого специфического c метода? Это O(n choose k), как описано в этом вопросе?

Какова временная сложность этого алгоритма для поиска всех комбинаций?

Есть ли какая-либо оптимизация, связанная с реализацией math.comb(), что уменьшает временную сложность до менее чем O(n choose k)?

Answer 1

У меня нет однозначного ответа, но math.comb(), кажется, медленная сторона:

Использовал math.comb() решить проблему Pascal Треугольник :

from math import comb

def get_row(k):
    row = [None for _ in range(k+1)]
    row[0], row[-1] = 1, 1
    for y in range(1, k):
        row[y] = comb(k, y)
    return row