数组递归子集计算复杂度分析

Question

我写了一个递归计算数组子集的代码。我对代码的复杂性有点困惑。我希望它的形式是T(n) = T(n-1) = O(n)请让我知道我是对还是错。谢谢你。

def subsets(arr):
"""
:param: arr - input integer array
Return - list of lists (two dimensional array) where each list represents a subset
TODO: complete this method to return subsets of an array
"""
if len(arr) == 1:
return [[], arr]

outs = []
elem = arr[0]
next_elems = arr[1:]
outs = subsets(next_elems)
for each_elem in outs: 
t1 = [elem] + each_elem 
outs = outs + [t1]

return outs

下面是代码的输入和输出示例:Arr = [9,12,15]输出= [[]，[15],[12],(12、15),[9],9、15,9、12,[9,12,15]]

Answer 1

递归关系是错误的，因为在对输入大小n-1递归调用函数后，您循环遍历所有2^(n-1)结果，并在每次迭代中创建一个大小为O(n)的新数组t1。所以递归关系应该是

T(0) = 1
T(n) = T(n-1) + n * 2^(n-1)

以来

lim { T(n), for n->infinity } = n * 2^(n-1),

这个关系的渐近解为

O(n * 2^(n-1)) = O(n * 2^n)