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

Question

我在采访中被问到提出了一个笛卡儿积的线性时间解决方案。我做了迭代方式O（mn）和一个也是O（mn）的递归解决方案。但我无法进一步降低复杂性。有没有人有关于如何改进这种复杂性的想法？也有人可以提出一个有效的递归方法？

Answer 1

还有mn结果;你必须做的最小工作是将每个结果写入输出。所以你不能比O(mn)做得更好。

Answer 2

我脑子里想到的这个问题是，“关于什么是线性的？”请记住，在数学中，所有变量都必须定义为有意义。大O符号也不例外。如果没有定义n，简单地说一个算法是O（n）是毫无意义的。

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