Big-O обозначение алгоритма перестановки в python itertools.permutation - PullRequest
Новая
       15

Big-O обозначение алгоритма перестановки в python itertools.permutation

2 голосов
/ 03 ноября 2019

Я пытался выяснить сложность времени проблемы перестановки в python. Но эта проблема выходит за рамки моих возможностей ... Кто-нибудь может мне помочь, пожалуйста?

Кстати, этот алгоритм является алгоритмом, используемым в методе pyter itertools.permutation.

Вкратцепохоже на ao (n ^ 2), но я не уверен, что временная сложность цикла for равна o (n). Цикл for не работает линейно ... 

def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

Ответы [ 2 ]

1 голос
/ 03 ноября 2019

Прежде всего, это итераторы, поэтому давайте предположим, что вы получаете полный результат с помощью list ().

Сложность перестановок ограничена математической формулой для числа перестановок n!/(n-r)!,n для r=1 и n! для r=n.

Для сравнения, O(n!) сложность хуже, чем O(2^n), что действительно плохо.

ВВ другой реализации, предложенной @jmullercuber, сложность еще хуже O(n^r) при использовании product и фильтрации результатов с повторяющимися индексами.

0 голосов
/ 03 ноября 2019

Отредактировано :

Не глядя слишком много, я должен догадаться, что алгоритм должен быть ограничен O(n!/(n-r)!), где n := len(interables), поскольку это - то, сколько существует различных перестановок. https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n. Максимум, когда r == n, это дает O(n!)

Глядя на другую реализацию перестановки, я получаю сложность времени O(n^r), которая составляет самое большее O(n^n), когда r == n

Полагаю, вы получили реализацию Python от https://github.com/python/cpython/blob/3.8/Doc/library/itertools.rst? Я получил свой результат, посмотрев на вторую / более простую реализацию на этой странице, скопированную ниже: 

def permutations(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    for indices in product(range(n), repeat=r):
        if len(set(indices)) == r:
            yield tuple(pool[i] for i in indices)

Существует один цикл for, поэтому сложность будет примерно на порядок, сколько раз вы имеетециклproduct вернет генератор, который выдаст n^r элементов на основе заданных параметров.

Это неоптимально, так как он вычисляет перестановки с заменами и использует if для фильтрации, чтобы получить перестановки без замен,Вот откуда взялся подход O(n^r).

Примечание: itertools фактически реализован в C, поэтому он может использовать алгоритм, отличный от того, что описан в Python, и, следовательно, это может неточно отражать действительную сложность itertools.permutation.

Также из-за генераторов и ленивых вычислений ваша программа не сталкивается с трудоемкостью сразу при вызове функции перестановки.

...