死磕算法-递归行为的实质
程序员文章站
2022-07-12 08:12:05
...
概述
递归用一句话概括,就是自己调用自己,而实现就是通过系统栈对函数的出栈和压栈操作。
用一个例子解释下递归的背后的实现
public static int getMax(int[] arr,int left,int right) {
if(left==right) {
return arr[left];
}
int mid = (left+right)/2;
int maxLeft=getMax(arr,left,mid);
int maxRight=getMax(arr,mid,right);
return Math.max(maxLeft, maxRight);
}
假设此时有这样一个数组{4,2,1,3},传入getMax(),left=0,right=3
- 判断left!=right,执行下一步
- 计算出mid为1
- 尝试获取maxLeft,进入getMax(arr,left,mid)之前,先将一开始调用的函数入栈(存入参数值mid=1,程序计数器保存函数当前执行到第几行)
- 第二次调用getMax后,传入的参数是(arr,left=0,right=mid=1),重复第二步计算mid,重复第三步进入getMax,并压栈
直到left==right,开始返回,系统栈开始弹栈,栈顶的函数先出栈,即getMax(arr,0,1),mid=0这个栈元素出栈,继续往下执行第x+1行,即int maxRight=getMax(arr,mid,right);
,传入arr,mid=0,right
之后继续执行第x+1行
直到递归完成。
递归用起来很好理解,要理解背后的执行流程就比较复杂,读者大概知道递归就是系统在不断地帮我们压栈出栈即可,每次压栈的信息包括程序计数器的内容(即函数执行到第几行),还有参数信息
可以简单理解下图
递归的时间复杂度:master公式的使用
T(N) = a*T(N/b) + O(Nd(额外时间复杂度)
- log(b,a) > d -> 复杂度为O(Nlog(b,a)
- log(b,a) = d -> 复杂度为O(N^d * logN)
- log(b,a) < d -> 复杂度为O(Nd
其中b:N/b为子样本容量,a为划分的样本个数
还是用一这例子解释下这个master公式
public static int getMax(int[] arr,int left,int right) {
if(left==right) {
return arr[left];
}
int mid = (left+right)/2;
int maxLeft=getMax(arr,left,mid);
int maxRight=getMax(arr,mid,right);
return Math.max(maxLeft, maxRight)
}
这里子样本容量为原样本容量的1/2,所以b为2;执行了两次子递归,所以a为2
这样的话,对数结果为1 ,而此处额外时间复杂度为1,因此1==1,符合第二种情况,之后代入公式即可。
上一篇: Helm部署和体验jenkins
下一篇: Java小练_面向对象-模拟迷你共享单车
推荐阅读