このコードのこのコードの複雑さは何ですか？

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

$ f（n）$ size $ 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）！$

あなたは簡単にこれを誘導で証明することができます。 sa $ f（n）= o（（n + 1）！）$ 。