파이썬에서 재귀 루프의 시간 복잡도를 어떻게 결정합니까?

Question

파이썬에서리스트의 모든 순열을 생성하는 시간 복잡도는 얼마입니까? 다음 코드는 시간 복잡성을 계산해야하는 코드입니다. 어떻게해야합니까?

def permute(list): 
    tot_list = [] 
    if len(list) == 1: 
     return [list] 
    for permutation in permute(list[1:]): 
     for i in range(len(list)): 
      tot_list.append(permutation[:i] + list[0:1] + permutation[i:]) 
    return tot_list 

Answer 1

이 함수를 분석 할 때 주된 문제는 많은 재귀 호출이 없지만 각 호출이 점점 더 커지고 더 큰 요소 목록을 반환한다는 점입니다. 특히, n! n 개의 요소 목록의 순열. 따라서 크기 n의 목록에서 재귀 호출을하면 n! 요소가 반환되었습니다.

이것이 런타임에 어떻게 영향을 미치는지 봅시다. 단 하나의 요소 목록이 있다면 시간 복잡도는 O (1)입니다. 그렇지 않은 경우 목록에 n + 1 개의 요소가 있다고 가정 해 보겠습니다. 그런 다음 알고리즘

1. 크기 n의 목록에서 재귀 호출을 작성합니다.
2. 반환되는 각 요소에 대해 가능한 모든 위치에서 목록의 첫 번째 요소를 연결합니다.
3. 결과를 반환합니다.

우리는 재귀의 각 단계에서 완료된 작업을 살펴봄으로써 재귀의 총 런타임을 분석 할 수 있습니다. 즉, 단계 (2)와 (3)에 집중할 것입니다.

2 단계에서 목록에 n + 1 개의 요소가 있으면 n! 재귀 호출에 의해 생성 된 순열. 각 순열에는 n 개의 원소가 있습니다. 각 순열에 대해 n + 1 개의 새로운 목록을 만들고, 각각의 목록에는 n + 1 개의 요소가 있습니다. 그러므로, 우리는 n! 반복 반복은 각각 (n + 1) 이 작동합니다. 결과적으로,이 레벨에서 수행 된 총 작업은 (대략적으로) (n + 1) & middot; 엔!. 우리는 (n + 1) & middot; 엔! = (n + 1) !, 따라서 수행 된 작업은 (n + 1) (n + 1)! 이것은 (n + 2)보다 작습니다! n + 1 개의 전체 요소가있을 때 수행되는 작업은 O ((n + 2)!)라고 말할 수 있습니다. (n! = o ((n + 2)!)이기 때문에 이것이 O (n!)라고 말할 수는 없습니다.

그래서 지금 우리는 수행 된 전체 작업이

1에 의해 주어진 (대략 말하기)이라고 말할 수있다! + 2! + 3! + ... + (n + 1)!

본인이 알고있는 한, 폐쇄 형 양식이 아닙니다. 그러나

1! + 2! + 3! + ... + (n + 1)!

< (n + 1)! + (n + 1)! + ... + (n + 1)!

= (n + 2) (n + 1)!

= (n + 2)!

그래서 전체 표현식은 O ((n + 2)!)입니다. 마찬가지로, 우리는 그 것이다

1! + 2! + 3! + ... + (n + 1)!

> (n + 1)!

따라서 전체 표현식은 Ω ((n + 1)!)입니다. 다른 말로하면, 진정한 해답은 (n + 1) 어딘가에 끼워진다 (asymptotically)! 및 (n + 2)! 따라서 런타임은 빠르게 변합니다.

희망이 도움이됩니다.