查找数组数组的笛卡尔积的时间复杂度

Question

final class Combination {

    public static void findCombinations(String[][] sets) {
        int combinations = 1;
        for(int i = 0; i < sets.length; combinations *= sets[i].length, i++);
        for(int i = 0; i < combinations; i++) {
            int j = 1;
            for(String[] set : sets) {
                System.out.print(set[(i/j)%set.length] + " ");
                j *= set.length;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
         findCombinations(new String[][]{{"a","b","c"}, {"d","e","i"}, {"f","g","h"}});
    }
  }

我的答案是这样的

   a d f 
   b d f 
   c d f 
   a e f 
   b e f 
   c e f 
   a i f 
   b i f 
   c i f 
   a d g 
   b d g 
   c d g 
   a e g 
   b e g 
   c e g 
   a i g 
   b i g 
   c i g 
   a d h 
   b d h 
   c d h 
   a e h 
   b e h 
   c e h 
   a i h 
   b i h 
   c i h

我想知道我的解决方案的时间复杂度以及是否有任何改进解决方案的方法。

Answer 1

它是 O(|first| * |second| * |third| * ...)，而你 无法在那个界限上改进，它的 Theta，不仅是 O。

单独的结果就那么大（在您的示例中为 27 = 3 * 3 * 3），您需要创建每个结果，这样您就不能比结果的大小更好。 Omega 边界结束。

O 部分非常简单，因为您的代码执行的所有子操作都在 Theta(1) 中。所以我们只需要考虑循环。您最内层的循环生成结果，每个结果打印一张。所以你的算法 是最优的 ，每个正确的结果迭代一次。您不会生成需要丢弃的无用对，也不会在它们之间使用任何非常量操作。由于仅结果的数量就属于上述复杂性，您的代码也是如此。

如前所述，对于精确的边界，我们需要包括每个子元素的大小。但是如果你更想要一个大小变量，比如说 n 你可以用最大数组的大小来限制其他大小：

n = max(|first|, |second|, |third|, ...)

然后你得到

Theta(n^x)

其中 x 是您传入的数组数量。因此在您的示例中它将是 Theta(n^3).

查找数组数组的笛卡尔积的时间复杂度

Finding the time complexity of cartesian product of array of arrays

java

performance

cartesian-product

time-complexity