递归Java方法S的时间复杂度计算：return语句运行时间判定疑问

先给出待分析的Java递归方法：

public static int S(int list[],int n) {
    if (n==1) {
        return list[1];
    } else {
        return (list[n] + S(list, n-1));
    }
}

我想要计算这个S方法的时间复杂度，但对else分支中return语句的运行时间计算存在疑问，请问应采用以下哪种递推式来定义时间复杂度？

• T(n) = T(n-1) + 3：T(n-1) + return本身的1个时间单位 + 调用list[n]的1个时间单位 + 加法操作的1个时间单位
• T(n) = T(n-1) + 2：T(n-1) + return本身的1个时间单位 + 加法操作的1个时间单位
• T(n) = T(n-1) + 2：T(n-1) + 调用list[n]的1个时间单位 + 加法操作的1个时间单位
• T(n) = T(n-1) + 1：T(n-1) + 加法操作的1个时间单位

分析与结论 #

从精确的操作计数角度，正确的递推式是第一个选项：T(n) = T(n-1) + 3。

原因在于else分支中，除了递归调用S(list, n-1)（对应T(n-1)），还包含三个独立的常数时间操作：

1. 访问数组元素list[n]，属于O(1)操作；
2. 执行加法运算，将list[n]与递归返回值相加，属于O(1)操作；
3. 执行return语句，将加法结果返回，属于O(1)操作。

需要补充的是：无论常数项是1、2还是3，最终推导的时间复杂度都是O(n)——因为渐近复杂度分析会忽略常数项的具体数值，只关注增长趋势。但如果要严格对应操作步骤的拆分，第一个递推式的描述最完整。

内容的提问来源于stack exchange，提问作者hasanghaforian