Сложность выполнения расчета перестановки с некоторыми изменениями

Question

У меня есть вопрос о сложности времени выполнения стандартного алгоритма поиска перестановок. Рассмотрим список A, найдите (и распечатайте) все перестановки его элементов.

Вот моя рекурсивная реализация, где printperm () печатает каждую перестановку:

def printperm(A, p):
    if len(A) == len(p):
        print("".join(p))
        return

    for i in range(0, len(A)):
        if A[i] != 0:
            tmp = A[i] # remember ith position
            A[i] = 0 # mark character i as used
            p.append(tmp) # select character i for this permutation
            printperm(A, p) # Solve subproblem, which is smaller because we marked a character in this subproblem as smaller
            p.pop() # done with selecting character i for this permutation
            A[i] = tmp # restore character i in preparation for selecting the next available character


printperm(['a', 'b', 'c', 'd'], [])

Кажется, что сложность среды выполнения равна O (n!), Где n - это размер A. Это происходит потому, что на каждом уровне рекурсии объем работы уменьшается на 1. Таким образом, верхний уровень рекурсии равен n объему работы, следующий уровень - n-1, следующий уровень - n-2 и т. д. Таким образом, общая сложность равна n * (n-1) * (n-2) ... = n!

Теперь проблема в выражении print("".join(p)). Каждый раз, когда эта строка запускается, она перебирает список, который перебирает весь список, который является сложностью n. Нет! количество перестановок списка размером n. Таким образом, это означает, что объем работы, выполненной оператором print("".join(p)), равен n! * N.

Увеличивает ли присутствие оператора print("".join(p)) сложность времени выполнения до O (n * n!) ?? Но это кажется неправильным, потому что я не запускаю оператор print при каждом вызове рекурсии. Где моя логика для получения O (n * n!) Ломается?

Answer 1

Ты в принципе прав! Возможная путаница возникает в вашем «... и следующий уровень - n-2 и так далее». «И так далее» означает, что на самом нижнем уровне рекурсии вы не выполняете O(1) работу, а скорее O(n) работаете над печатью. Таким образом, общая сложность пропорциональна

n * (n-1) * (n-2) ... * 2 * n

, что равно n! * n. Обратите внимание, что .join() на самом деле не имеет значения для этого. O(n) работа также потребует просто print(p).

РЕДАКТИРОВАТЬ: Но это не совсем правильно, по другой причине. На всех уровнях выше уровня print вы делаете

for i in range(0, len(A)):

и len(A) не меняются. Так что каждый уровень выполняет O(n) работу. Надо отметить, что чем глубже уровень, тем больше нулей в A, и, следовательно, чем меньше работа цикла, тем не менее, O(n) все равно просто перебирает range(n).