这个幂集函数的时间复杂度是多少？
What is the time complexity of this powerset function?
我从 leetcode https://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) ？我不知道这很难说。
如果我们假设内循环在每次到达break之前要经过大约一半的range(n)，那么这就是O(n/2*2^n)，实际上仍然是O(n*2^n)。这适用于循环的任何固定部分，所以即使它平均是 range(n) 的十分之一而不是一半，它仍然是 O(n*2^n)
我从 leetcode https://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) ？我不知道这很难说。
如果我们假设内循环在每次到达break之前要经过大约一半的range(n)，那么这就是O(n/2*2^n)，实际上仍然是O(n*2^n)。这适用于循环的任何固定部分，所以即使它平均是 range(n) 的十分之一而不是一半，它仍然是 O(n*2^n)