线性时间的算法来计算笛卡尔积 [英] Linear time algorithm to compute cartesian product

问题描述

有人问我，在接受采访时拿出与笛卡尔积线性时间的解决方案。我做了迭代的方式O（MN）和递归解决方案也这也是O（MN）。但我无法进一步降低复杂性。有没有人对这种复杂性，如何进行改进？同时任何人都可以提出一个有效的递归的方法呢？

I was asked in an interview to come up with a solution with linear time for cartesian product. I did the iterative manner O(mn) and a recursive solution also which is also O(mn). But I could not reduce the complexity further. Does anyone have ideas on how this complexity can be improved? Also can anyone suggest an efficient recursive approach?

推荐答案

有明尼苏达州的结果;你所要做的最小的工作是编写的每个结果输出。所以你不能做的比好O（MN）。

There are mn results; the minimum work you have to do is write each result to the output. So you cannot do better than O(mn).

这篇关于线性时间的算法来计算笛卡尔积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！