本文详解 java 中递归实现数组反转的算法时间复杂度，证明其为 o(n)，并通过等价迭代形式直观说明递归调用次数与输入规模的线性关系。

本文详解 java 中递归实现数组反转的算法时间复杂度，证明其为 o(n)，并通过等价迭代形式直观说明递归调用次数与输入规模的线性关系。

该递归函数 reverse(int[] arr, int start, int end) 的核心逻辑是：每次交换 arr[start] 和 arr[end]，然后递归处理子区间 [start+1, end−1]，直到 start >= end 时终止。

我们来逐步分析其时间复杂度：

• 每次递归调用执行常数时间操作（三次赋值 + 一次比较），即 O(1)；
• 递归深度由区间长度决定：初始调用为 [0, n−1]，下一层为 [1, n−2]，依此类推；
• 每次调用使区间长度减少 2，因此总共递归调用次数为 ⌊n/2⌋ + 1（含终止条件的一次判断），即 Θ(n) 次调用；
• 总时间 = 调用次数 × 单次耗时 = Θ(n) × O(1) = O(n)。

值得注意的是，该算法不产生额外空间开销（除递归栈），但空间复杂度为 O(n)（最坏递归深度为 n/2，对应栈帧数量），而时间复杂度仅关注计算量，故仍为 O(n)。

为更清晰理解，可将递归完全转为迭代——它本质上就是一个双指针遍历：

public static void reverseIterative(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (i < j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

该迭代版本显式执行 ⌊n/2⌋ 次循环，显然时间复杂度为 O(n)；而原递归版本在逻辑和执行步数上与其一一对应，因此时间复杂度完全一致。

✅ 关键结论：

• 不要被“递归”表象迷惑——若每次递归只推进常数距离（如本例中 start+1 和 end−1），且问题规模线性缩减，则时间复杂度通常为 O(n)；
• 分析递归时间复杂度时，优先写出递推式：
    T(n) = T(n−2) + O(1) ⇒ 解得 T(n) = O(n)；
• 实际工程中，迭代实现更优（避免栈溢出风险，尤其对超大数组）。

综上，该递归数组反转算法的时间复杂度为 O(n)，准确且最优——因为至少需访问并交换 ⌊n/2⌋ 对元素，任何正确解法都必须达到此下界。