递归的时间复杂度（Master 公式）
原创递归的时间复杂度（Master 公式）
原创
?
Master公式是什么？
我们在解决算法问题时，经常会用到递归。递归在较难理解的同时，其算法的复杂度也不是很方便计算。而为了较为简便地评估递归的算法复杂度，Master公式。
Master公式
含义
- T(N):
- 表示当输入规模为 N 时，算法所需的时间复杂度。
- N 通常代表问题的规模，比如数据的数量、数组的长度、图的顶点数等。
- a:
- 表示子问题的数量。在分治算法中，a 常常代表每次递归调用产生的子问题数量。
- 例如，在归并排序中，a 的值为 2，因为每次递归调用会将问题分为两个子问题。
- T(N/b):
- 表示每个子问题的时间复杂度。
- b 是问题规模减小的因子，即每次递归调用时，问题规模都会减少到原来的 1/b。
- 例如，在归并排序中，每次递归调用都会处理数组的一半，所以 b 的值为 2。
- O(N^d):
- 表示除了递归调用之外，算法在每次递归步骤中所做的额外工作的时间复杂度。
- O(N^d) 是除了递归调用之外的时间开销的上界。
- d 是一个常数，表示额外工作的时间复杂度与 N 的关系。
其中的a、b、d都是常数
结论：
- 当
时，
；
- 当
时
，
；
- 当
时，
；
注意
子问题规模必须等分，不管你是分成几部分
应用举例
问题：在一个长度为 N 的数组中，求最大值
方法一
public static int getMax(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
return process(arr, 0, arr.length - 1);
}
public static int process(int[] arr, int start, int end) {
if (start == end) {
return arr[start];
}
// int mid = (start + end) / 2;
int mid = start + ((end - start) >> 1);
int left = process(arr, start, mid);
int right = process(arr, mid + 1, end);
return Math.max(left, right);
}
这个是一个很简单的递归，将数组划分成左半部和右半部，求出左边最大值，在求出右边的最大值，最后比较左右的最大值，求出整个数组的最大值。因为将数组划分为左右两部分，所以子问题的规模为（N/2）即b = 2，又有int left = process(arr, start, mid);和int right = process(arr, mid + 1, end);的两次调用，所以a = 2，剩下来，有return arr[start]、int mid = start + ((end - start) >> 1);、return Math.max(left, right);三个常数级的操作，所以为 O(1) d = 0。
所以带入到 Master 公式：
进入结论 2
当
时
，
；
所以复杂度为：
方法二
public static int process2(int[] arr, int start, int end) {
if (start == end) {
return arr[start];
}
// int mid = (start + end) / 2;
for (int i = 0; i < arr.length; i++) {
System.out.println("啥也不干,就是输出！");
}
int mid = start + ((end - start) >> 1);
int left = process(arr, start, mid);
int right = process(arr, mid + 1, end);
return Math.max(left, right);
}和方法一唯一区别的地方是多加了一个 for 循环 每次循环数组的长度 a b 同方法一不变，但是 d 在三个常数操作外 额外增加了一个 O(N) 的操作 所以 d = 1。所以 Master 公式为：
进入结论 3
当
时
，
；
所以时间复杂度为：O(N * logN)
注意事项
我们上面的两种方法都是每次求解子问题时求将问题对等的分成两份，倘若将数据分成三份，左边求三分一的数据右边求三分之二的数据，这样子的话不符合相同规模的划分，就不能使用 Master 公式来计算时间复杂度
?
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。