这个powerset函数的时间复杂度是多少？

Question

我从leetcodehttps://leetcode.com/problems/subsets/submissions/解决了这个问题（powerset函数），下面是我的解决方案：

    def subsets(nums):
        res = []
        n = len(nums)
        for subset_id in range(2**n):
            tmp = []
            for index in range(n):
                if 1 << index > subset_id:
                    break
                if subset_id >> index & 1:
                    tmp.append(nums[index])
            res.append(tmp)
        return res

我很难分析这段代码的时间复杂度，语句if 1 << index > subset_id: break在O(n*2^n)下，我想，但是它会一直到O(2^n)吗？我不知道这很难说。你知道吗

Answer 1

如果我们假设内环在每次击中break之前要经过range(n)的一半，那么这就是O(n/2*2^n)，实际上仍然是O(n*2^n)。这适用于循环的任何固定部分，因此即使它平均是range(n)的十分之一而不是一半，它仍然是O(n*2^n)