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)即使它们的大小没有限制的。

Answer 2

我也有同样的问题（对于 itertools.permutations）并且很难追踪复杂性。这让我使用 matplotlib.pyplot 将代码可视化；代码片段如下所示result=[]import matplotlib.pyplot as pltimport mathx=list(range(1,11))def permutations(iterable, r=None):     count=0    global result    pool = tuple(iterable)    n = len(pool)    r = n if r is None else r    if r > n:        return    indices = list(range(n))    cycles = list(range(n, n-r, -1))    yield tuple(pool[i] for i in indices[:r])    while n:        for i in reversed(range(r)):            count+=1            cycles[i] -= 1            if cycles[i] == 0:                indices[i:] = indices[i+1:] + indices[i:i+1]                cycles[i] = n - i            else:                j = cycles[i]                indices[i], indices[-j] = indices[-j], indices[i]                yield tuple(pool[i] for i in indices[:r])                break        else:            resulte.append(count)            returnfor j in x:    for i in permutations(range(j)):        continuex=list(range(1,11))plt.plot(x,result)从图中可以看出，时间复杂度为 O(n!) 其中 n=Input Size