所以我正在寻找不同的方法来计算 n 数组的笛卡尔积，并且我遇到了使用以下代码的相当优雅的解决方案(此处为 SO):
import itertools
for array in itertools.product(*arrays):
print array
查看 python doc page (我正在使用 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 循环)。
我错了吗？
最佳答案
你完全正确。也就是说，在两个数组输入的特殊情况下，两个数组的大小都是 n。在 k 个大小为 n[i] 的数组的一般情况下，i 在 1..k 它将是 O(所有 n[i] 的乘积)。
为什么会这样，为什么没有进一步优化的方法？
嗯，在这种情况下，输出的大小直接是这个“所有 n[i] 的乘积”，这取决于我们正在讨论的函数的性质. Python 通过将其实现为生成器使这一点更加明显。因此，对于每个元素，此生成器都会生成一个元素，最终生成的元素数将与所述产品一样多。
当然，如果某个东西如此明显地做了 x 次，它的效率不可能比 O(x) 好。如果每个元素的工作量也取决于输入大小，情况可能会更糟。所以，准确地说，这里每个元素的工作量取决于我们放入的数组数量，所以真正的工作量是
O(k × 所有n[i]的乘积)
关于python - Python 的 itertools.product() 的效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31960583/