递归时间复杂度分析 && 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);
}
}
如何求上面的算法的时间复杂度呢？
这就要使用master公式了。
master公式：
T(n) = a * T(n/b) + O(
n
d
n^{d}
nd)
首先使用这个公式的条件是 ：该递归函数中若存在多个递归调用，那么这些递归调用的机会必须是相等的。
比如上面这个，包含两个递归，且两个递归的机会都是相等的各占1/2。而b代表调用的机会，n/b就为1/2。
int leftMax = sumMax(arr, left, mid);
int rightMax = sumMax(arr, mid + 1, right);
a就是函数中使用了几次递归函数，a = 2。
O(
n
d
n^{d}
nd) 代表的是除去递归函数中的递归部分，其余的时间复杂度为多少，很明显是O(1)，此时 d = 0。
上面的例子用master表达式表示就是：
T(n) = 2 * T(n/2) + O(1)
此时我们用一套规律来计算它的时间复杂度：
对于T(n) = a * T(n/b) + O(
n
d
n^{d}
nd)，
- 若
l
o
g
b
a
log_{b}^{a}
logba < d，时间复杂度为 O(
n
d
n ^ {d}
nd)
- 若
l
o
g
b
a
log_{b}^{a}
logba > d, 时间复杂度为 O(
n
l
o
g
b
a
n ^ {log_{b}^{a}}
nlogba)
- 若
l
o
g
b
a
log_{b}^{a}
logba == d, 时间复杂度为 O(
n
d
n ^ {d}
nd *
l
o
g
2
n
log_{2}^{n}
log2n)
所以，例子中的递归时间复杂度是：O(n)
