什么决定了递归关系中的常量？

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) 

希望它清除的东西。