查找数组所有可能的子数组的时间复杂度

问题描述 投票:0回答:2

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

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);
    }

根据我的理解,由于存在三个FOR循环,所以时间复杂度将为O(N ^ 3)。

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

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

algorithm data-structures time-complexity powerset binomial-theorem
2个回答
0
投票

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

不正确。

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

相比之下,幂集还将包含discontiguous子序列,这意味着它们包含两个元素,但不包括它们之间的所有元素。


我还应注意,只有On 2)个子数组,如果您找到其他表示它们的方式,则可以在O中找到它们(n 2)时间,而不是您发布的代码的On 3)时间。 (特别是,您需要一个表示形式,该表示形式允许您重复使用列表的共享部分,而不必每次都复制所有必需的元素。)相反,如果您坚持使用代码中的表示形式,其中每个列表都有一个单独的副本,找到所有子集实际上将需要On·2 n])时间,而不仅仅是O(2 n] >)时间。

幂集查找子序列而不是子数组。子数组是连续的,但是子序列可以是不连续的。因此,查找数组的子序列和子数组并不相同。


0
投票

幂集查找子序列而不是子数组。子数组是连续的,但是子序列可以是不连续的。因此,查找数组的子序列和子数组并不相同。

© www.soinside.com 2019 - 2024. All rights reserved.