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

查看:117
本文介绍了python中的“ itertools.combinations”的计算复杂度是多少?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆