Qual è la complessità del tempo di questo pezzo di codice?

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

.

Sto cercando di capire la complessità del tempo di questo codice come sto lavorando per studiare domande di codifica e la loro complessità del tempo e sono riuscito a risolvere questo problema di permutazione usando la ricorsione come è stato richiesto, ma mi chiedo come faccio a farloDeterminare accuratamente la Big- $ o $ complessità del tempo per questo come è un mix di ricorsione seguita da un ciclo iterativo.Apprezzerei davvero qualche utile input su questo.

Answer 1

Let $ f (n) $ Sii la risposta per un ingresso di ingresso di dimensioni $ N $ . Quindi abbiamo la seguente equazione:

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

Questo perché si chiama la funzione per un ingresso di dimensioni $ N - 1 $ che dà $ f (n -1) $ , quindi si intera su tutte le permutazioni di dimensioni $ N - 1 $ che ci sono $ (n - 1)! $ Tali permutazioni, e quindi si intera la posizione del nuovo elemento, che ci sono $ N $ tali posizioni.Questo ci dà:

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

Puoi facilmente dimostrare questo per induzione. Quindi $ f (n)= o ((n + 1)!) $ .