SilverLining's Blog

递归与时间复杂度

递归

通俗地讲,递归就是自己调用自己。递归函数的意义,是将一个大问题,分解为若干个同等算法,但规模更小的子问题。通过解决一系列小范围的子问题,总而在大范围上解决整个问题。

求数组的最大值

举个例子,求一个数组中的最大值。常规的做法是扫描整个数据,用一个变量记录下最大值,时间复杂度为 O(N)

而递归的思想是,要求一个数组中的最大值,假设有 10 个数,那么我只要找出左边 5 个数的最大值,和右边 5 个数的最大值,一比较,就可以得到整个数组的最大值。

因此这个问题被分解为了,求两个长度为 5 的数组中的最大值,这样一个规模更小但算法相同的子问题。

接着看这个 5 个数的数组,要想求他的最大值,我们可以再分一半,如果知道了左边两个数的最大值,和右边 3 个数的最大值,就可以求出这个数组的最大值。

继续看左边的 2 个数,分解为 2 个只有 1 个数的数组,此时我们得到这个问题的最小子问题(base case),当数组只有一个元素时,最大值就是他自己。

public class RecursiveGetMax {
    public static int getMax(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("Invalid arguments");
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int left, int right) {
         if (left < 0 || right > arr.length - 1 || left > right) {
            throw new IllegalArgumentException("Invalid arguments");
        }
        if (left == right) {
            return arr[left];
        }
        int mid = left + ((right - left) >> 1);
        int leftMax = process(arr, left, mid);
        int rightMax = process(arr, mid + 1, right);
        return Math.max(leftMax, rightMax);
    }
}

时间复杂度

递归算法的时间复杂度可以用 Master 公式求得,当其满足以下形式时:

T(N) = a \cdot T(\frac {N} {b}) + O(N^{d})

其中:

则有:

\begin{aligned} \\ (1)\ \log_{b}{a} > d,\ T(N) = O(N^{\log_{b}{a}}) \\ (2)\ \log_{b}{a} < d,\ T(N) = O(N^d) \\ (3)\ \log_{b}{a} = d,\ T(N) = O(N^d \cdot \log_{2}{N}) \\ \end{aligned}

对于上面这个求最大值的例子,子问题的规模为 1/2,递归调用 2 次,除递归以外的操作时间复杂度为 O(1)

b = 2,\ a = 2,\ d = 0 \\ \log_{b}{a} = 1,\ d = 0,\ \log_{b}{a} > d

此时

\Rightarrow T(N) = O(N) \\

因此,递归求数组最大元素的操作,时间复杂度也是 O(N)