itertools的计算复杂度是多少。python中的组合？

Question

itertools。python中的combines是查找所有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

我也有同样的问题（对于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)

itertools的时间复杂度图。置换

从图中可以看出，时间复杂度为O（n！）其中n=输入大小

Answer 2

我会说它是θ[r（n选择r）]，n选择r部分是生成器必须产生的次数，也是外部而的次数迭代。

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

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

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