python中的“ itertools.combinations”的计算复杂度是多少？

python中的“ itertools.combinations”的计算复杂度是多少？

我要说的是

θ[r (n choose r)]

，

n choose r

部分是生成器必须进行

yield

的次数以及外部

while

迭代的次数。

在每次迭代中，至少

r

需要生成长度的输出元组，它给出了附加因子

r

。其他内部循环也将在

O(r)

每个外部迭代中进行。

这是假定元组的生成实际上是实际的，

O(r)

并且

O(1)

在给定算法中的特定访问模式的情况下，列表的获取/设置实际上至少平均而言是平均的。如果不是这种情况，那么仍然

Ω[r(n choose r)]

可以。

像往常一样，在这种分析中，我假设所有整数运算

O(1)

的大小均不受限制。