python - 计算笛卡尔积的线性时间算法

Question

我在一次采访中被要求为笛卡尔积提出一个线性时间的解决方案。我做了迭代方式 O(mn) 和递归解决方案也是 O(mn)。但我无法进一步降低复杂性。有没有人知道如何改善这种复杂性？也有人可以提出一种有效的递归方法吗？

Answer 1

有mn结果；您要做的最少工作是将每个结果写入输出。所以你不能做得比O(mn).

Answer 2

读到这里，我想到的问题是，“关于什么是线性的？” 请记住，在数学中，所有变量都必须定义为有意义。Big-O 表示法也不例外。如果 n 没有定义，简单地说算法是 O(n) 是没有意义的。

假设这个问题是有意义的，而不是一个错误，我猜他们希望你要求澄清。另一种可能性是，他们想看看你在遇到不可能的情况时会如何反应。