Сложность выполнения рекурсивной функции перестановки

Question

Я написал этот код, который возвращает всю перестановку предоставленной строки. Теперь я хочу вычислить сложность во время выполнения и мне нужна помощь в этом.

Код рекурсивно вызывает функцию permutationRecursively N раз (для каждого символа строки, т. Е. St), а затем есть два цикла for каждый перебирает все перестановки, возвращаемые обратно из рекурсивного вызова (то есть для a это будет ['a'] или для ab это будет ['ab', 'ba'] и так далее), а затем каждая пара перестановок. Я действительно запутался в этой части. Какова будет сложность этой конкретной c части?

Я предполагаю, что для всех рекурсивных вызовов это будет O(N), а затем для внутренних циклов это будет O(A*B). Таким образом, общая сумма будет O(N*A*B). Это правильно?

def permutationRecursively(st):
    if(len(st) < 2):
        return [st]
    else:
        permutations = permutationRecursively(st[0:-1])
        newPermutations = []
        wordToInsert = st[-1]
        for permutationPair in permutations:
            for index in range(len(permutationPair)+1):
                newPermutations.append(permutationPair[0:index]+wordToInsert+permutationPair[index:])          
        return newPermutations

start_time = time.time()
permutationRecursively("abbc")
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

Для подобных задач я нахожу, что простой подсчет итераций самого внутреннего l oop даст вам довольно хорошее представление о сложности.

count = 0
.
.
.

for index in range(len(permutationPair)+1):
    global count
    count += 1
    newPermutations.append(permutationPair[0:index]+wordToInsert+permutationPair[index:])          

С этой модификацией у нас есть таблица отсчетов для разных входов:

• "a": 0
• "ab": 2
• "ab c": 8
• "abcd": 32
• "abcde": 152
• "abcdef": 872
• "abcdefg": 5912
• "abcdefgh": 46232

Начиная с последней записи, мы вычитаем запись перед ней. Это дает:

• "a": 0
• "ab": 2 - 0 = 2
• "ab c": 8 - 2 = 6
• "abcd": 32 - 8 = 24
• "abcde": 152 - 32 = 120
• "abcdef": 872 - 152 = 720
• "abcdefg": 5912 - 872 = 5040
• "abcdefgh": 46232 - 5912 = 40320

Учитывая, что мы работаем с перестановками, числа выше должны быть знакомы. Проще говоря, это факториал длины каждого входа.

Таким образом, сложность выглядит примерно так:

O(n! + (n - 1)! + ... + 2!)

Может быть, это сводится к чему-то хорошему, например, к сумме от 1 до n. Вот что WolframAlpha говорит об этом:

Yikes! Это не легко потреблять. Я догадываюсь, что первый член будет доминировать при увеличении n. Помните, что мы имеем дело с асимптотическим поведением c, поэтому нас интересует только то, что происходит, когда n становится большим.

Давайте проверим эту догадку, посмотрев на соотношение factorail(n) / sum([factorial(x) for x in range(2, n + 1)])

from math import factorial

def get_ratio(n):
    return factorial(n) / sum([factorial(x) for x in range(2, n + 1)])

[get_ratio(x) for x in range(2, 30)]
[1.0, 0.75, 0.75, 0.7894736842105263, 0.8256880733944955, 0.8525033829499323,
 0.8721232047066967, 0.8869942705176088, 0.8986822892623713, 0.9081347182982339,
  0.9159495525890125, 0.9225247281105151, 0.9281368938946185, 0.932985094435074,
   0.9372165386007432, 0.9409426073299031, 0.9442492142738237, 0.947203738596165,
    0.9498597948796416, 0.9522605938189509, 0.9544413593967874, 0.9564310992723437,
     0.9582539225228436, 0.9599300347361424, 0.9614764993074284, 0.9629078267955898,
      0.9642364361184396, 0.9654730190404553]

По мере увеличения n мы видим, что основная часть нашего выражения происходит от первого члена, как мы и подозревали.

Таким образом, в конечном итоге сложность (не удивительно, я мог бы добавить) вашего алгоритма:

O (n!)