Quelle est la complexité de temps de ce morceau de code?

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

J'essaie de déterminer la complexité temporelle de cette pièce de code, car je travaille sur l'étude de questions de codage et de leur complexité de temps et j'ai réussi à résoudre ce problème de permutation à l'aide de la récursion nécessaire, mais je me demande comment puis-jeDéterminez avec précision la Big- $ O $ Complexité du temps pour cela, car il s'agit d'un mélange de récursivité suivie d'une boucle itérative.J'apprécierais vraiment une contribution utile à ce sujet.

Answer 1

let $ f (n) $ est la réponse à une entrée de taille $ n $ . Ensuite, nous avons l'équation suivante:

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

C'est parce que vous appelez la fonction d'une entrée de taille $ n - 1 $ qui donne $ f (n -1) $ , alors vous itérez sur toutes les permutations de taille $ n - 1 $ qui il y a $ (n - 1)! $ de telles permutations, puis vous ithérez-vous sur la position du nouvel élément, ce qu'il y a $ n $ ces postes.Cela nous donne:

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

Vous pouvez facilement le prouver par induction. Donc $ f (n)= o ((n + 1)!) $ .