다음 프로그램의 복잡성은 얼마나됩니까? O (log n)이 맞습니까?

Question

배열의 모든 짝수의 합계를 찾습니다. 합계를 구하는 재귀 프로그램. 이 프로그램의 시간 복잡성은 무엇이며 어떻게 분석합니까?

def sumEven(arr): 
    if len(arr) == 0: 
     return 0 
    if len(arr) == 1: 
     if arr[0]%2 == 0: 
      return arr[0] 
     else: 
      return 0 
    else: 
     mp = len(arr)//2 
     return sumEven(arr[0:mp]) + sumEven(arr[mp:]) 

Answer 1

그것은 여전히 ​​(n/2 당신이 더 정확하게하려면) O(n)입니다. 각 단계마다 작업을 절반으로 나눕니다.하지만 체인을 올라갈 때 재결합해야합니다. #even 값을 수행하지 않고 모든 짝수 값을 추가 할 수는 없습니다 - 최소 1 개의 더하기 연산. 이는 주어진 추가가 대략 동일한 크기의 피연산자와 일치한다는 확률을 향상시킵니다. 여기서 소스 피연산자가 동일한 크기를 유지할 때 반복적으로 하나의 누적 피연산자가 계속 증가합니다.

evenness 요소를 무시하고 배열의 모든 숫자를이 방식으로 합산한다고 생각하십시오. 8 개의 요소가있는 경우 짝수 요소를 홀수 (4 개의 요소를 남기고 4 개의 연산)에 추가 한 다음 짝수 번째 결과를 홀수 결과에 추가합니다 (두 개의 요소를 남기는 두 개의 연산). 그런 다음 두 개의 나머지 값을 함께 추가합니다 (하나의 수술, 대답을 남겨둔다). 8 개의 값을 추가하려면 4 + 2 + 1 == 7 작업을 수행했습니다.

elems = [1,2,3,4,5,6,7,8] 

accumulator = elems[0] 
# Loop runs seven times, for all but first element, so seven additions performed 
for operand in elems[1:]: # Ignore the slice cost here; avoidable, but irrelevant 
    accumulator += operand