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

Question

itertools.combinationsin python 是一个强大的工具，用于查找r项的所有组合，但是，我想知道它的计算复杂度。

假设我想知道n和r方面的复杂性，当然它会给我n项列表中的所有r项组合。

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

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)

Answer 1

我会说它是?[r (n choose r)]，n choose r部分是生成器必须执行yield的次数以及外部while迭代的次数。

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

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

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