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 plt

import math

x=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)

            return

for j in x:

    for i in permutations(range(j)):

        continue

x=list(range(1,11))

plt.plot(x,result)

从图中可以看出，时间复杂度为 O(n!) 其中 n=Input Size