这段代码的时间复杂程度是多少？

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

.

我正在努力弄清楚这段代码的时间复杂性，因为我正在研究编码问题和他们的时间复杂性，并且我设法使用所需递归来解决这个排列问题，但我想知道如何我准确地确定Big- $ O $ 时间复杂性，因为它是次数的递归混合，后跟迭代循环。我真的很欣赏一些有用的输入。

Answer 1

let $ f（n）$ 是输入大小的答案 $ n $ 。 然后我们有以下等式：

$ f（n）= f（n - 1）+（n - 1）！* n= f（n - 1）+ n！$

这是因为您称之为大小输入的函数 $ n - 1 $ ，它给出 $ f（n - 1）$ ，然后您迭代大小的所有排列 $ n - 1 $ 其中有 $（n - 1）！$ 此类排列，然后您遍历新元素的位置，其中有 $ n $ 这样的位置。这给了我们：

$ f（n）= [\ sum_ {i= 1} ^ n i！] <（n + 1）！$

您可以通过归纳轻松证明这一点。 所以 $ f（n）= o（（n + 1）！）$ 。