循环中递归函数的大O复杂度

Question

我遇到了解决Leetcode问题的方法，该方法发现了不断增加的子序列。我认为该解决方案的复杂度为O（N！），可能无法扩展到大型数组。

您能详细说明一下如何为此计算复杂度吗？

public class IncreasingSubsequences {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[]{4, 6, 7, 8};
        findSubsequences(a);
    }

    public static List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new LinkedList<>();
        helper(new LinkedList<Integer>(), 0, nums, res);
        return res;
    }

    // [4, 6, 7, 7]
    private static void helper(LinkedList<Integer> list, int index, int[] nums, List<List<Integer>> res) {

        if (list.size() > 1){
            res.add(new LinkedList<Integer>(list));
            System.out.println(Arrays.toString(list.toArray()));
        }

        Set<Integer> used = new HashSet<>();

        for (int i = index; i < nums.length; i++) {
            if (used.contains(nums[i]))
                continue;
            if (list.size() == 0 || nums[i] >= list.peekLast()) {
                used.add(nums[i]);
                list.add(nums[i]);
                helper(list, i + 1, nums, res);
                System.out.println("Will remove" + list.get(list.size() - 1));
                list.remove(list.size() - 1);
                //System.out.println(">>" + Arrays.toString(list.toArray()));
            }
        }
    }

}

Answer 1

您怀疑时间和内存的复杂度几乎是O（N！）。更精确地，附加存储器为O（N * 2 ^N），时间为O（M * 2 ^N）。其中，M是原始列表nums的长度，N是其中唯一值的数目（s.t. N <= M）。

您意识到对结果列表中的每个值都调用一次递归函数后，就很容易得出复杂度表达式。结果列表包含输入值集的所有可能子集。实际上，该程序将打印并返回原始集的幂集。

如果原始集合包含N（唯一）个值，则幂集合包含2 ^N

个唯一集。这也是结果列表的长度，以及对递归函数的调用次数。

另一种查看方式是长度为N的所有二进制数的集合，其中0位表示未选择该值，而1表示该值在子集中。该视图给出相同的结果。每位恰好是N位可能值的一半，即为1。这意味着平均而言，N位数字的一半为1。类似地，一半的原始值在一个平均子集中。 [易于使它更加正式]。

根据以上结论，得出所有返回列表的长度为2 ^N

* N / 2，即O（N * 2 ^N）。这是结果的附加内存复杂性，以及打印输出的复杂性。如果M> N，则在最坏的情况下，所有重复项都在末尾。这将导致所有递归调用最后都具有其他M-N操作。由于存在2 ^N个调用，因此时间复杂度变为O（N * 2 ^N）+O（（M-N）* 2 ^N）= O（M * 2 ^N）。