问Python3.8中`math.comb()`的时间复杂度是多少？

EN

我没有一个明确的答案，但math.comb()似乎有点慢：

​

​

用math.comb()解决一个Pascal三角形problem

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

我相信它是2N，如果你看一下nCr的手动代码，你会注意到一个用于factorial(n)的while循环，一个用于factorial (r)的while循环，还有一个用于factorial (n-r)的while循环。

因此，用于计算r和n-r的阶乘的while循环等价于阶乘(n)。

因此，它基本上运行了2N次，但是，如果您修改代码以在单个循环中存储事实(R)和事实(n-r)，同时查找事实(N)。那么也许它可以是O(N)。