반복 관계에서 상수를 결정하는 것은 무엇입니까?

Question

나는 다음과 같은 알고리즘을 말해봐 :

ArraySum (A, n) 
    if n = 1 
     return A[0] 
    return A[n-1] + ArraySum(A, n-1) 

그래서 재발 관계가

 | c1   n = 1 
T(n) = | 
     | T(n-1) + c2 n > 1 

내가 c1 = 0 및 c2 = 3 같은 일부 자료를보고하게,하지만 나는 c1 및 c2 결정에 대해 어떻게 가야합니까?

Answer 1

우리가 시간 복잡성에 관해서 말하면, c1과 c2는 모두 n과 관계없이 일정합니다. 그래서 그들은 O (1)입니다. 그래서

 | O(1)   n = 1 
T(n) = | 
     | T(n-1) + O(1) n > 1 

그리고 해결에

.

T(n) = O(n) 

희망 사항은 삭제됩니다.