이 코드 조각의 Big-O는 무엇입니까?

Question

최근에 나는이 질문이있는 시험을 보았습니다. g의 시간 복잡도는 얼마입니까?

int f(int *arr, int n, int m) 
{ 
    if(n == 0) 
    { 
     if(m == 0) 
      return 3; 

     return arr[m] + f(arr, n, m - 1); 
    } 

    return f(arr, n - 1, m); 
} 

int g(int *arr, int n) 
{ 
    return f(arr, n, n); 
} 

이제 명확 F와 아무것도 2 * n을 호출이 있기 때문에 저와 제 친구들의 대부분은 O (n)을 대답하지만, 교수의 대답은 (n은^2) O했다. 누가 나에게 맞는지 설명 할 수 있습니까? 그 사람이라면 이유를 설명해 주시겠습니까?

Answer 1

편집 : 게시물에

, 내가 틀린 문제를 해결하는 것을 알고 있습니다. 내부 함수 호출이 f(arr, m, m - 1) 일 때이를 해결하려고했습니다. 이 경우 시간 복잡도는 실제로 O (n²)입니다. 질문이 게시 된 방식으로 시간 복잡성은 O (n)입니다. 그러나이 교수는 교수가 잘못 이해 한 방법 일 가능성이 큽니다. 따라서 다음 질문에 대한 답은 참고 용으로 작성된 것입니다. n == 0 n은 스택을 호출하는 것을 의미 f() n 번 반복적으로

1. 전화 :

   는 촬영 단계를 고려하십시오.

2. 이제 가장 낮은 함수 호출에서 if 문을 입력 할 수 있습니다.
3. f()을 다시 호출하여 m을 줄이지 만 m을 두 번째 인수로 호출하여 원래의 n 값을 유지합니다.
4. 이 '새'재귀 스택에서 m을 1 씩 줄이기 전에 먼저 f()을 n (또는 m) 번 다시 호출해야합니다.
5. m == 0 번으로 돌아 오면 되돌릴 수 있습니다.

모든 '단위'는 f()에 대한 하나의 호출을 나타내는이 그래프를보십시오. n == 0 일 때, 우리는 세 번째 인자를 다시 호출하고 m을 1 씩 줄이므로 레벨을 떨어 뜨립니다.

이 그래프에서 사각형의 영역 n * m와 m == n 때문에 , 즉 f()은 n² 배라는 것을 의미하고, 코드는 O (n²) 시간 복잡도를 갖는다.