递归实现Java整数数组反转的时间复杂度求解

先看你提供的递归反转数组代码：

class Test2 {
    public static int[] reverse(int[] arr, int start, int end) {
        if (start < end) {
            int temp;
            temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

            reverse(arr, start + 1, end - 1);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5 };
        int[] value = reverse(arr, 0, arr.length - 1);
        for (int i = 0; i < value.length; i++) {
            System.out.println(value[i]);
        }
    }
}

时间复杂度分析过程 #

1. 单次递归的操作成本 #

每次进入reverse方法，当start < end时，只会执行3次赋值操作（交换两个数组元素），这部分属于常数时间操作，记为O(1)。之后调用一次递归，处理范围缩小的子数组。

2. 递归调用的次数 #

假设数组长度为n，初始调用参数是start=0，end=n-1：

• 每递归一次，start加1、end减1，处理的数组范围长度减少2；
• 当start >= end时递归终止，此时不再执行交换和递归。

总有效递归（执行交换的次数）为floor(n/2)：

• 若n是偶数（比如n=4），会执行2次交换；
• 若n是奇数（比如n=5），会执行2次交换；
  这个次数和数组长度n呈线性相关。

3. 递推式推导 #

设T(n)为反转长度为n的数组的时间复杂度：

• 边界条件：当n <= 1时，T(n) = O(1)（无需交换，直接返回数组）；
• 递推关系：当n > 1时，T(n) = T(n-2) + O(1)（交换一次后，递归处理长度为n-2的子数组）。

展开递推式：

• 若n为偶数，n=2k：T(n) = k*O(1) = O(k) = O(n)；
• 若n为奇数，n=2k+1：T(n) = k*O(1) + O(1) = O(k) = O(n)。

结论 #

这段递归反转数组代码的时间复杂度是O(n)，其中n是数组的长度。

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