Что такое временная сложность этого куска кода?

Question

def find_perms(s):
    """
    Finds permutations of the given string.
    >>> find_perms("abc")
    ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']
    """
    if len(s) == 1:
        return [s]
    elif len(s) == 2:
        return [s[0]+s[1], s[1]+s[0]]
    else:
        perm = find_perms(s[0:len(s)-1])
        last_char = s[len(s)-1]
        lst = []
        for strings in perm:
            for index in range(len(strings)+1):
                string = strings[:index] + last_char + strings[index:]
                lst.append(string)
        return lst

.

Я пытаюсь выяснить временную сложность этого куска кода, поскольку я работаю над изучением вопросов кодирования и их временной сложности, и мне удалось решить эту проблему перестановки, используя рекурсию, как это было необходимо, но мне интересно, как я могуТочно определите больший - $ O $ Сложность времени для этого, как это смесь рекурсии, за которым следует итерационный цикл.Я бы очень ценил, что некоторые полезные вклад на это.

Answer 1

Пусть $ f (n) $ Будьте ответ для ввода размера $ n $ . Тогда у нас есть следующее уравнение:

$ f (n)= f (n - 1) + (n - 1)!* n= f (n - 1) + n! $

Это потому, что вы вызываете функцию для ввода размера $ n - 1 $ , который дает $ f (n - -1.n - 1)! $ Такие перестановки, а затем вы итерации по положению нового элемента, которые существуют $ n $ такие позиции.Это дает нам:

$ f (n)= [\ sum_ {i= 1} ^ n i!] <(n + 1)! $

Вы можете легко доказать это по индукции. Таким образом, $ f (n)= o ((n + 1)!) $ .