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

Question

在一次面试中，我被问到如何用线性时间来解决笛卡尔积的问题。我用了一种迭代的方法，复杂度是O(mn)，还做了一个递归的解决方案，复杂度也是O(mn)。但是我没法进一步降低这个复杂度。有没有人有什么想法可以改善这个复杂度？还有谁能建议一个高效的递归方法？

Answer 1

我看到这个问题时，脑海中浮现的第一个想法是：“线性是相对于什么来说的？”记住，在数学中，所有的变量都必须被定义，才能有意义。大O符号也不例外。如果不定义n，单单说一个算法是O(n)是没有意义的。

假设这个问题是有意义的，而不是个错误，我猜他们可能是想让你去请求进一步的解释。还有一种可能是，他们想看看你在面对一个不可能的情况时会怎么反应。

Answer 2

总共有 mn 个结果；你至少得把每个结果都写到输出里。所以你做得再好也不可能比 O(mn) 更快。