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

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) 结果并在每次迭代时创建一个新数组 t1大小 O(n)。所以递归关系应该是

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)

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

Complexity Analysis of recursive subset calculation of an array

python

algorithm

time-complexity