4

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

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

查看python 文档页面（我使用的是 2.7，顺便说一句）itertools.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 循环）。

我错了吗？

4

1 回答 1

2

你是绝对正确的。也就是说，在输入两个数组的特殊情况下，大小都是n。在大小为n [ i ] for i in 1.. k的k数组的一般情况下，它将是 O（所有n [ i ] 的乘积）。

为什么会这样，为什么没有办法进一步优化呢？

好吧，在这种情况下，输出的大小直接是“所有n [ i ] 的乘积”，这取决于我们正在讨论的函数的性质。Python 通过将其实现为生成器使这一点更加明显。所以对于每个元素，这个生成器产生一个元素，最终它会产生与所述产品一样多的产生元素。

当然，如果某样东西显然做了x次，它的效率不会比 O( x ) 好。如果每个元素的工作量也取决于输入大小，情况可能会更糟。所以，准确地说，这里每个元素的工作量取决于我们输入的数组数量，所以真正的工作量是

O( k × 所有n [ i ]的乘积)

于 2019-03-21T09:24:03.077 回答