在一次采访中,我被要求为笛卡尔积提出一个线性时间的解决方案。我采用了迭代方式 O(mn) 和递归解决方案,这也是 O(mn) 。但我无法进一步降低复杂性。有谁知道如何改善这种复杂性?还有人可以建议一种有效的递归方法吗?
有mn结果;您要做的最少工作是将每个结果写入输出。所以你不能做得更好O(mn).
mn
O(mn)