알고리즘의 시간 복잡도

Question

다음은 오름차순으로 목록을 정렬하는 코드입니다. 함수 내에서 함수를 사용했습니다. 이제이 함수의 시간 복잡도를 계산하고 싶습니다. 내 측면에서 함수 "정렬"이 루프를 완료 할 때마다 "통합"함수가 호출된다는 계산을했습니다. 따라서이 함수에서는 매 함수 두 개가 사용됩니다. 그래서이 함수의 복잡도는 O (nlog (n))라고 결론을 냈습니다. 이 장을 처음 사용합니다. 그래서 이런 종류의 복잡성을 계산하는 방법을 알고 싶습니다. 위의 대답은 단지 나의 근사치입니다. 그리고 나는 진정한 답을 모르거나 해결책이나 암시를 가지고 있지 않습니다. 그래서 당신이 줄 때마다 대답을 기술하십시오. 감사합니다. . 내 코드는 다음과 같습니다.

def sort(lst): 
    def unite(l1, l2): 
     if len(l1) == 0: 
      return l2 
     elif len(l2) == 0: 
      return l1 
     elif l1[0] < l2[0]: 
      return [l1[0]] + unite(l1[1:], l2) 
     else: 
      return [l2[0]] + unite(l1, l2[1:]) 

    if len(lst) == 0 or len(lst) == 1: 
     return lst 
    else: 
     front = sort(lst[:len(lst)/2]) 
     back = sort(lst[len(lst)/2:]) 

     L = lst[:] # the next 3 questions below refer to this line 
     return unite(front, back) 

Answer 1

첫 번째 단계는 실제 작업은 당신이 때마다 새 목록을 작성하고 있기 때문에 n^2 작업을 수행 코드의 unite 단계에서 수행되고 있음을 주목하는 것입니다.

W(n) = 2W(n/2) + n^2 

당신이 길이 n/2의있는 목록에 두 번 재귀하고 다시 가입하는 n^2 작업을하고 있기 때문에 :

그래서 당신은 실제로 함수가하고있는 일의 양에 대한 빠른 재발을 작성할 수 있습니다.

이제 재귀 트리를 고려해보십시오. 트리의 특정 레벨 (i 레벨이라고 함)에서는 2^i * (n/2^i)^2 작업을 수행하고 있습니다. 각 레벨에서 O(n^2)의 작업을 수행 중이므로 log(n) 레벨이 있으므로 O(n^2log(n)) 작업을 수행하고 있습니다.

그러나 함수를 작성하여 훨씬 빠르게 실행되도록하는 방법이 있습니다 (O(n) 시간). 이 경우, 위와 비슷한 분석을 통해 O(nlog(n)) 작업을 수행 할 수 있습니다.

Answer 2

이 n 요소 벡터에서 실행되는 시간은 T (n)입니다.

T(n) = 2 T(n/2) + n 

    = 2 [2 T(n/4) + n/2] + n 

    = 4 T(n/4) + 2n 

    = 4 [2 T(n/8) + n/4] + 2n 

    = 8 T(n/8) + 3n 
    ........ 

    = 2k T(n/2k) + k n 

    = 2log2 n T(1) + (log2n) n because T(1)=O(1) 

    = n + n log2 n  

    = O(n log n) 

정렬 솔루션 재귀 함수의 복잡성을 쉽게 기억할 수 있습니다. T (선택 정렬) = O (n^2) 및 T (병합 정렬) = O (nlogn). 분명히 코드는 병합 정렬 유형입니다.

Answer 3

위의 코드의 시간 복잡도 (공간 복잡성이 아님)는 O(nlog(n))입니다.

는 시작시 목록에서 n 요소가 있고 우리는 반복적으로 front과 O(log(n)) 단계를 만드는 back에 n/2 요소마다에 그 목록을 나눕니다. 이제 각 O(log(n)) 단계에 대해 l1 및 l2의 각 요소를 반복하여 unite의 함수를 한 번만 실행하면 unite의 함수가 O(n)이됩니다.

따라서, O(log(n)) 나누기와 O(n) 단결 단계를 사용하면이 알고리즘은 시간 복잡성이 O(nlog(n))이됩니다.

다른 답변은 O(n^2) 인 unite 함수의 공간 복잡성에 대해 논의하고 있지만 질문 제목은 공간 복잡성에 관한 것이 아니라 시간 복잡성에 대해 분명하게 묻습니다.