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

itertools.combinationspython 是一个强大的工具，可以找到所有组合r但是，我想了解它的条款计算复杂度.

假设我想知道以下方面的复杂性n and r，当然它会给我所有r列表中的术语组合n terms.

根据官方文档，这是粗略的实现。

def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

我想说的是θ[r (n choose r)], the n choose r部分是发电机必须的次数yield以及外部的次数while迭代。

在每次迭代中至少输出长度为r需要生成，这给出了附加因子r。其他内循环将是O(r)每个外部迭代也是如此。

这是假设元组生成实际上是O(r)并且列表 get/set 确实是O(1)至少平均而言，考虑到算法中的特定访问模式。如果情况并非如此，那么仍然Ω[r (n choose r)] though.

像往常一样，在这种分析中，我假设所有整数运算都是O(1)即使它们的大小没有限制。