0

根据从给定数组中查找所有可能的子数组的实现，如下所示：

public class AllPossibleSubArray {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        List<List<Integer>> result = new ArrayList<>();

        for (int len = 0; len <= arr.length; len++) {
            if (len == 0) {
                result.add(new ArrayList<>());
            } else {
                for (int i = 0; i < arr.length - len + 1; i++) {
                    List<Integer> temp = new ArrayList<>();
                    for (int j = i; j < i + len; j++) {
                        temp.add(arr[j]);
                    }
                    result.add(temp);
                }
            }
        }

        result.forEach(System.out::println);
    }

据我了解，时间复杂度为 O(N^3)，因为有三个 FOR 循环。

但是这个问题只不过是一个幂集，即从给定的集合中找到所有可能的子集。从网上的各种论坛，幂集的时间复杂度为 2^N（二项式展开），与 O(N^3) 不同。

我是否缺少一些基本知识？

4

1 回答 1

3

但是这个问题只不过是一个幂集，即从给定的集合中找到所有可能的子集。

这是不正确的。

您发布的代码只能找到连续的子数组，这意味着从一个索引到另一个索引的所有元素的列表。

相比之下，幂集还包括不连续的子序列，即包含两个元素但不包括它们之间的所有元素的子序列。

我还应该注意，只有O ( n 2 ) 个子数组，如果您找到一种不同的方式来表示它们，您可以在O ( n 2 ) 时间内找到它们，而不是O ( n 3 ) 时间作为您的代码'已经发布了。（具体来说，您需要一个允许您重用列表的共享部分的表示，而不必每次都复制所有必需的元素。）相比之下，如果您坚持代码中的表示，其中每个列表都有一个不同的副本，找到所有子集实际上需要O ( n ·2 n ) 时间，而不仅仅是O (2n ) 时间。

于 2020-02-24T06:04:37.230 回答