このコードのこのコードの複雑さは何ですか?
-
29-09-2020 - |
質問
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 $ の時間の複雑さを決定します。私はこれに関するいくつかの役に立つ入力に本当に感謝します。
解決
$ 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)!)$ 。
所属していません cs.stackexchange