¿Cuál es la complejidad del tiempo de esta pieza 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

Estoy tratando de averiguar la complejidad del tiempo de esta pieza de código, ya que estoy trabajando en estudiar preguntas de codificación y su complejidad de tiempo y me las arreglé para resolver este problema de permutación utilizando la recursión, como se requirió, pero me pregunto cómo puedoDetermine con precisión el Big- $ o $ complejidad de tiempo para esto, ya que es una combinación de recursión seguida de un bucle iterativo.Realmente apreciaría algunos aportes útiles en esto.

Answer 1

Permitir $ f (n) $ ser la respuesta para una entrada de tamaño $ n $ . Luego tenemos la siguiente ecuación:

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

Eso es porque llamas a la función para una entrada de tamaño $ n - 1 $ que da $ f (n -1) $ , luego itera sobre todas las permutaciones de tamaño $ n - 1 $ que hay $ (N - 1)! $ tales permutaciones, y luego itera sobre la posición del nuevo elemento, que hay $ n $ tales posiciones.Esto nos da:

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

Puede probar esto fácilmente por la inducción. Así $ f (n)= o ((n + 1)!) $ .