python - 生成所有大小为 K 的子集的时间复杂度

Question

从长度为 n 的输入列表生成所有大小为 k 的子集的代码的时间复杂度是多少？

def generate(l: list, k: int) -> list: #length of list l is defined to be n
    if k == 0 or l == [] or len(l) < k: # Check if list is empty or k == 0 or invalid
        return [[]]
    elif k == 1: # Base case: k == 1
        return [[elem] for elem in l]
    else: # Recursive case
        result = [] # Result contains the subsets
        for ind, first_elem in enumerate(l[:-k + 1]):
            generated = generate(l[ind+1:], k - 1) # Generate all subsets of sublist of size k - 1
            modified = [[first_elem] + lst for lst in generated] # Add first element to all subsets
            result += modified
        return result

当我在我的计算机上运行它时，我发现当 2k = n 时，运行时间在 k 和 n 方面呈指数增长。也就是说，每次 k 增加 1 且 n 增加 2 时，运行时间大约会翻两番。例如，n = 18 和 k = 9 时的运行时间为 85 ms，比 n = 16 和 k = 8 (20 ms) 时的运行时间长 4 倍，比 n = 14 和 k = 时的运行时间长 4 倍7（5 毫秒）。

在维基百科上，它说中心二项式系数大约是序列中每个元素的四倍。这是否意味着我的代码的运行时间大约是可能的子集数量（n 选择 k）？不确定如何分析得出运行时。

标签： pythonalgorithmrecursiontime-complexityruntime