问题描述
itertools.combinations 是查找 r 术语所有组合的强大工具，但是，我想知道它的计算复杂度。
itertools.combinations in python is a powerful tool for finding all combination of r terms, however, I want to know about its computational complexity.
假设我想了解 n 和 r 的复杂性，当然它将给我 n 术语列表中的所有 r 术语组合。
Let's say I want to know the complexity in terms of n and r, and certainly it will give me all the r terms combination from a list of 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选择r）] ， n选择r 部分是生成器必须达到 yield 以及外部 迭代的次数。
I would say it is θ[r (n choose r)], the n choose r part is the number of times the generator has to yield and also the number of times the outer while iterates.
迭代至少需要生成长度为 r 的输出元组，这将产生附加因子 r 。其他内部循环也将是每个外部迭代 O（r）。
In each iteration at least the output tuple of length r needs to be generated, which gives the additional factor r. The other inner loops will be O(r) per outer iteration as well.
这是假定元组生成实际上是 O（r），并且列表获取/设置的确至少平均是 O（1）给定算法中的特定访问模式。如果不是这种情况，则仍然Ω[r（n选择r）] 。
This is assuming that the tuple generation is actually O(r) and that the list get/set are indeed O(1) at least on average given the particular access pattern in the algorithm. If this is not the case, then still Ω[r (n choose r)] though.
和往常一样在这种分析中，我假设所有整数运算都为 O（1），即使它们的大小不受限制。
As usual in this kind of analysis I assumed all integer operations to be O(1) even if their size is not bounded.
这篇关于python中的“ itertools.combinations”的计算复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！