递归时间复杂度分析 && master公式

递归时间复杂度分析 && master公式

我们先来看一道递归的例子：

我们要寻找一个数组的最大值，要求用递归的方法求出

代码如下：

/**
 * @author `dongxu.kwb`
 * @date `2022/8/30`
 */
public class SumMax {
    public static void main(String[] args) {
        int[] arr = {79,3213,3,5,45,65};
        System.out.println(sumMax(arr, 0, arr.length - 1));
    }

    /**
     * 求数组arr再[left, right]上的最大值
     * @param arr 传入的数组
     * @param left 数组最左面的值
     * @param right 数组最右面的值
     * @return
     */
    public static int sumMax(int[] arr, int left, int right) {
        if (left == right) return arr[left]; //递归中止条件，当分到只剩一个数时
        int mid = left + ((right - left) >> 1); //取中点
        int leftMax = sumMax(arr, left, mid);
        int rightMax = sumMax(arr, mid + 1, right);
        return Math.max(leftMax, rightMax);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

如何求上面的算法的时间复杂度呢？

这就要使用master公式了。

master公式：

​ T(n) = a * T(n/b) + O($n^d$)

首先使用这个公式的条件是 ：该递归函数中若存在多个递归调用，那么这些递归调用的机会必须是相等的。

比如上面这个，包含两个递归，且两个递归的机会都是相等的各占1/2。而b代表调用的机会，n/b就为1/2。

        int leftMax = sumMax(arr, left, mid);
        int rightMax = sumMax(arr, mid + 1, right);
1
2

a就是函数中使用了几次递归函数，a = 2。

O($n^d$) 代表的是除去递归函数中的递归部分，其余的时间复杂度为多少，很明显是O(1)，此时 d = 0。

上面的例子用master表达式表示就是：

​

​ T(n) = 2 * T(n/2) + O(1)

此时我们用一套规律来计算它的时间复杂度：

对于T(n) = a * T(n/b) + O($n^d$)，

• 若 $lo{g}_b^a$ < d，时间复杂度为 O($n^d$)
• 若 $lo{g}_b^a$ > d, 时间复杂度为 O($n^{lo{g}_b^a}$)
• 若 $lo{g}_b^a$ == d, 时间复杂度为 O($n^d$ * $lo{g}_2^n$)

所以，例子中的递归时间复杂度是：O(n)