이 코드의 시간 복잡성은 무엇입니까?

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

.

코딩 질문과 시간의 복잡성을 연구하고있는 것처럼이 코드의 시간 복잡성을 알아 내려고 노력하고 있습니다. 그리고 나는 재귀를 사용 하여이 순열 문제를 해결할 수 있었지만 어떻게 해야할지 궁금합니다.빅 $ o $ 시간 복잡성이 반복 루프가 뒤 따르는 시간 복잡성을 정확하게 결정합니다.나는 이것에 대한 도움이되는 입력에 대해 정말로 감사드립니다.

Answer 1

$ 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)!) $