子集问题解决方案的时间复杂度

Question

我想在 leetcode 上验证 space 和我解决 subsets 问题的时间复杂度。由于堆栈 space，space 复杂度为 O(N)。时间复杂度为 O(2^N)，因为每个第 i 层的工作是向列表中添加 2^i 个元素。所以从 0 到 N 对 2^i 求和得到 O(2^N)。我对么？我不确定，因为 3 个官方解决方案的时间复杂度为 O(N*2^N).

import java.util.ArrayList;
import java.util.List;

public class Solution {
    // Space Complexity: O(N) 
    // Time Complexity: 2^0 + 2^1 + ... + 2^N = O(2^N) 
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(List.of());
        subsetsHelper(nums, 0, subsets);
        return subsets;
    }

    private void subsetsHelper(int[] nums, int index, List<List<Integer>> subsets) {
        if (index >= nums.length) return;
        int current = nums[index];
        int initialSize = subsets.size();
        for (int i = 0; i < initialSize; i++) {
            var list = subsets.get(i);
            var listCopy = new ArrayList<>(list);
            listCopy.add(current);
            subsets.add(listCopy);
        }
        subsetsHelper(nums, index + 1, subsets);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.subsets(new int[]{0, 1, 2}));
    }

}

Answer 1

我想通了为什么它是 2^N 乘以 N。

对于subsetsHelper()，在第i级，子集的数量是2^(i-1)。而其中每个subsetList的大小为O(N)。当我在 subsetsHelper() 中将每个子 subsetList 的大小加倍（代码中从 list 到 listCopy）时，它的时间复杂度是 O(N*2^i).

并且由于函数被调用了N次，所以subsets()的时间复杂度为O(N*(2^0 +...+2^(N-1)) = O(N*2^N)

子集问题解决方案的时间复杂度

Time Complexity of Subsets problem solution

algorithm

time-complexity