Блог

Какова временная сложность этого кода для генерации всех подмножеств размера k из входного списка длины n?

 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
 

Когда я запускаю его на своем компьютере, я обнаруживаю, что время выполнения экспоненциально увеличивается с точки зрения k и n, когда 2k = n. То есть каждый раз, когда k увеличивается на 1, а n увеличивается на 2, время выполнения увеличивается примерно в четыре раза. Например, время выполнения при n = 18 и k = 9 составляет 85 мс, что в 4 раза больше времени выполнения при n = 16 и k = 8 (20 мс), что в 4 раза больше времени выполнения при n = 14 и k = 7 (5 мс).

В Википедии говорится, что центральный биномиальный коэффициент примерно вчетверо увеличивается на элемент последовательности. Означает ли это, что время выполнения моего кода соответствует порядку числа возможных подмножеств (n выберите k)? Не уверен, как аналитически вывести время выполнения.