python - Python的itertools.product()的效率

因此，我正在研究不同的方法来计算n个数组的笛卡尔积，我遇到了使用以下代码的相当优雅的解决方案（这里是这样的）：

import itertools
    for array in itertools.product(*arrays):
        print array

查看python doc page（我使用的是2.7，btw）foritertools.product()，它表示代码等价于以下内容：

def product(*args, **kwds):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

（它确实注意到以下几点：此函数相当于以下代码，只是实际实现不会在内存中生成中间结果：）
我不是一个CS的人-所以我很难估计这个算法的效率。我的第一个猜测是O(n^2)（由于嵌套for循环）。
我错了吗？

最佳答案

你完全正确。也就是说，在两个数组输入的特殊情况下，两个数组的大小都是n。在k个数组的一般情况下，1..k中i的大小为n[i]的i将是o（所有n[i]的乘积）。
为什么是这样，为什么没有办法进一步优化？
在这种情况下，输出的大小直接是这个“n[i]的乘积”，这取决于我们讨论的函数的性质。python将其实现为一个生成器，从而使这一点更加明显。因此，对于每个元素，这个生成器生成一个元素，最终生成的元素将与所述产品一样多。
当然，如果某物明显做了x次，它的效率不会比o（x）更好。如果每个元素的工作也取决于输入大小，情况可能会更糟。所以，准确地说，这里每个元素的工作量取决于我们放入的数组的数量，所以真正的工作量是
o（k×n[i]的乘积）