python中的“ itertools.combinations”的计算复杂度是多少？ [英] What is the computational complexity of `itertools.combinations` in python?

问题描述

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”的计算复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！