这篇文章是看了“左程云”老师在b站上的讲解之后写的, 自己感觉已经能理解了, 所以就将整个过程写下来了。
这个是“左程云”老师个人空间的b站的链接, 数据结构与算法讲的很好很好, 希望大家可以多多支持左程云老师, 真心推荐.
https://space.bilibili.com/8888480?spm_id_from=333.999.0.0
1. 介绍递归
利用求一个数组中的最大值来理解递归：求 arr = [4, 2, 6, 1], 求这个数组中的最大值.
1.1 代码实例
这个代码真是很简单, 就不进行逻辑讲解了, 直接看就看明白了, 而且下面的递归决策图和递归的系统栈的调用图相信已经说的非常非常明白了!!! (两个结合起来看, 一定是能看懂的).
多画递归决策图, 这样也能很好地帮助大家理解递归.
public static int maxValue(int[] arr) {
return f(arr, 0, arr.length - 1);
}
// arr[l....r]范围上的最大值
public static int f(int[] arr, int l, int r) {
if (l == r) {
return arr[l]; // 简单到不能再简单的状态, 已经不能继续往下分了,(base case)
}
int m = (l + r) / 2;
int lmax = f(arr, l, m);
int rmax = f(arr, m + 1, r);
return Math.max(lmax, rmax);
}
public static void main(String[] args) {
int[] arr = { 3, 8, 7, 6, 4, 5, 1, 2 };
System.out.println("数组最大值 : " + maxValue(arr));
}
递归决策图
递归在系统栈中的调用
2.1 压栈：将递归改为非递归
任何递归函数都可以改为非递归, 不用系统帮你压栈, 自己利用内存空间压栈就行了 (哪怕是原原本本的和系统栈一样也行).
系统栈是固定大小的(比较小), 内存也是固定大小 (但是很大),
工程和笔试中需不需要改递归函数在最开始的图片上都有说明, 就不多废话了.
2. master 公式
使用 master 公式的意义：满足这个 master 公式的实例可以直接确定时间复杂度.
2.1 第一个例子
用上面的代码当成例子解释：有一个数组：arr[l...r], 我们将这个数组分成一半一半了, 然后从左边一半找到最大值和右边一半找到最大值, 然后从这两个部分找到最大值.
所以利用 master公式：T(N) = T(N/2) + T(N/2), 这个是前面的部分, 后面的部分是：除了递归(子过程调用)的部分, 剩下的部分的时间复杂度是：O(1) (因为所有的操作都是O(1)级别的).
所以最后的 master公式：T(N) = T(N/2) + T(N/2) + O(1).
master公式：T(N) = 2 * T(N/2) + O(1). 所以此时：a = 2, b = 2, c = 0(因为N^c, N^0 = 1),
2.2 第二个例子
还是用上面的代码当成例子解释：有一个数组：arr[l...r], 我们将这个数组左边是 2/3, 右边也是 2/3,
分别从左边和右边寻找最大值, 最后找到最大值, 这样肯定是也能找到的.
这样的 master 公式是：T(N) = 2 * T(N * 2/3) + O(1). 此时：a = 2, b = 3/2, c = 0. (注意：我们这里的公式是：N * ?, 但是原理的公式是：N/?, 所以要取倒数).
2.3 第三个例子
还是用上面的代码当成例子解释：有一个数组：arr[l...r], 我们将这个数组分成一半一半了, 然后从左边一半找到最大值和右边一半找到最大值, 然后从这两个部分找到最大值, 但是此时我就是想在最后遍历一遍数组
下面是代码：
public static int maxValue(int[] arr) {
return f(arr, 0, arr.length - 1);
}
// arr[l....r]范围上的最大值
public static int f(int[] arr, int l, int r) {
if (l == r) {
return arr[l]; // 简单到不能再简单的状态, 已经不能继续往下分了,(base case)
}
int m = (l + r) / 2;
int lmax = f(arr, l, m);
int rmax = f(arr, m + 1, r);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
return Math.max(lmax, rmax);
}
public static void main(String[] args) {
int[] arr = { 3, 8, 7, 6, 4, 5, 1, 2 };
System.out.println("数组最大值 : " + maxValue(arr));
}
这个时候的 master公式 = 2 * T(N/2) + O(n), 因为此时我加入了一个 for循环, 所以对应的, 除了子过程之外的时间复杂度是：O(n), 此时：a = 2, b = 2, c = 1.
当然, 要是我想用两个 for循环, 这样做 c = 2 了.
2.4 第四个例子
还是用上面的代码当成例子解释：有一个数组：arr[l...r], 我们将这个数组分成左边 2/3, 右边是：1/3, 此时就不能用 master公式 了, 因为两边的子问题已经不一样(不等规模)了, 一个是 2/3, 另一个是 1/3, 所以就不能使用了.
2.5 使用 master 公式计算时间复杂度
这没啥能记笔记的, 直接用下面的公式算就行了.
2.6 补充 (直接记住就行了)
