이 코드의 시간 복잡성은 무엇입니까?
-
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
.
코딩 질문과 시간의 복잡성을 연구하고있는 것처럼이 코드의 시간 복잡성을 알아 내려고 노력하고 있습니다. 그리고 나는 재귀를 사용 하여이 순열 문제를 해결할 수 있었지만 어떻게 해야할지 궁금합니다.빅 $ o $ 시간 복잡성이 반복 루프가 뒤 따르는 시간 복잡성을 정확하게 결정합니다.나는 이것에 대한 도움이되는 입력에 대해 정말로 감사드립니다.
해결책
$ f (n) $ 크기 $ n $ 의 입력에 대한 답변이되도록합니다. 그런 다음 우리는 다음과 같은 방정식을 가지고 있습니다 :
$ f (n)= f (n - 1) + (n - 1)!* n= f (n - 1) + n! $
$ n - 1 $ 의 입력을위한 함수를 호출하기 때문에 $ f (n-1) $ , 그런 다음 $ (n - 1)! $ 그러한 순열, 그리고 당신은 $ n $ 과 같은 새로운 요소의 위치를 반복합니다.이것은 우리에게 다음을 제공합니다 :
$ f (n)= [\ sum_ {i= 1} ^ n i!] <(n + 1)! $
유도에 의해 쉽게 이것을 증명할 수 있습니다. 따라서 $ f (n)= o ((n + 1)!) $
제휴하지 않습니다 cs.stackexchange