이 재귀 알고리즘의 시간 복잡도는 어떻게 계산합니까?

Question

다음 코드 조각의 시간 복잡도는 어떻게 계산합니까? m이 n에 가깝다고 가정하십시오. 내가 얻은 것은 f (n) = 2 * f (n-1)이다. 따라서 시간 복잡도는 f (n) = O (2^n)입니다. 내가 맞습니까?

int uniquePaths(int m, int n) { 
    if (m < 1 || n < 1) return 0; 
    if (m == 1 && n == 1) return 1; 
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); 
} 

Answer 1

다음 내용에는 약간의 변화가 있습니다.하지만 본질적으로 옳은 것 같습니다.

호출 트리의 모든 리프가 총 결과에 1을 기여하므로 리프 수는 uniquePaths (m, n)입니다. uniquePaths (m, n) == "m + n-2는 n-1을 선택"하기 때문에 m과 n이 비슷한 경우 알고리즘의 실행 시간은 대체로 중심 이항 계수 "2n choose n"이됩니다. 이것은 O (4^n).