Qual é o tempo de complexidade este pedaço de código?

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

Eu estou tentando descobrir o tempo de complexidade este pedaço de código como estou trabalhando, estudando a codificação de questões e o seu tempo de complexidade e eu consegui resolver este problema de permutação utilizando a recursividade como era necessário, mas eu estou querendo saber como faço para determinar, com precisão, o grande-$O$ tempo de complexidade para isto, pois é uma mistura de recursão seguido por um loop iterativo.Eu realmente aprecio alguns útil sobre isso.

Answer 1

Deixe $f(n)$ ser a resposta para uma entrada de tamanho $n$.em seguida, temos a seguinte equação:

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

Isso é porque você chamar a função para uma entrada de tamanho $n - 1$ o que dá $f(n - 1)$, e , em seguida, você iterar sobre todas as permutações de tamanho $n - 1$ que há $(n - 1)!$ tais permutações e, em seguida, você iterar sobre a posição do elemento novo, que não são $n$ tais posições.Isso nos dá:

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

Você pode facilmente provar por indução.Então, $f(n) = O((n + 1)!)$.