Временная сложность этой рекурсивной функции генератора k-комбинаций Python

Я искал алгоритм k-комбинации Python и нашел здесь эту маленькую красоту https://stackoverflow.com/a/2837693/553383< /а>

Есть идеи о его T(n) и/или временной сложности?

Вот код, который вы найдете по ссылке выше:

def choose_iter(elements, length):
    for i in xrange(len(elements)):
        if length == 1:
            yield (elements[i],)
        else:
            for next in choose_iter(elements[i+1:len(elements)], length-1):
                yield (elements[i],) + next
def choose(l, k):
    return list(choose_iter(l, k))

python algorithm asymptotic-complexity
person Manis    schedule 28.04.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Если предположить, что эта функция действительно генерирует все возможные комбинации длины k, временная сложность этой функции равна O(n!/[(n-k)!k!] * k^2).

Есть ровно O(n!/[(n-k)!k!]) k-комбинаций, и мы генерируем каждую из них.

Давайте посмотрим на поколение каждого. Это делается путем создания кортежа итеративно. Сначала добавляется 1-й элемент, затем 2-й, затем 3-й и так далее.

Однако создание кортежа длиной k равно O(k), и мы фактически получаем O(1+2+...+k) за создание каждого кортежа. Поскольку O(1+2+...+k)=O(k^2), а мы делаем это для каждого кортежа, мы можем сделать вывод, что общая сложность этой функции равна O(n!/[(n-k)!k!] * k^2).

person amit    schedule 28.04.2014
comment
Я думаю, что ваш расчет сложности может не учитывать стоимость срезов в каждом рекурсивном вызове. elements[i+1:] имеет время выполнения O(len(elements)-i), но я не уверен, как многочисленные вызовы объединяются для каждого i и каждого уровня рекурсии. - person Blckknght; 29.04.2014
comment
@Blckknght Каждый рекурсивный вызов - это O (1) [проходит некоторое постоянное количество ссылок]. так что вы должны были добавить добавочный коэффициент k, но это просто даст вам O(n!/[(n-k)!k!] * k^2 + n!/[(n-k)!k!] * k), который все еще находится в O(n!/[(n-k)!k!] * k^2). Узким местом в создании каждой комбинации является итеративное объединение элементов в кортеж. - person amit; 29.04.2014