Java教程

递归过程以及递归master公式

本文主要是介绍递归过程以及递归master公式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

递归过程以及递归master公式

递归过程

1. 举个栗子

使用递归方式找到数组中最大的元素,代码如下:

public class Recursion {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 5, 3, 1, 5, 6};
        System.out.println(process(arr, 0, arr.length - 1));
    }

    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1);	// 中点
        int leftMax = process(arr, L, mid);	//	找到左边部分最大值
        int rightMax = process(arr, mid + 1, R); //	找到右边部分最大值
        return Math.max(leftMax, rightMax);	//	返回两者中更大的那一个
    }
}

2. 解释说明

以 arr = new int[]{1, 3, 7, 5, 6, 2} 来说明(配合下图一起食用,效果更佳):

最开始调用方法为 p ( arr, 0, 5),(因为参数 arr 始终没有发生改变,之后方法简写一下,省略其中的 arr)

然后 p (0, 5) 会先调用 p (0, 2) 去找左边部分最大值 , p (0, 2) 会调用 p (0, 1) 去找左边部分最大值

p (0, 1) 会继续调用 p (0, 0),p(0, 0) 返回值 arr[0] , p(0, 1) 就可以进入到右边部分找最大值,即调用 p (1, 1) ,p (1, 1) 返回 arr[1] 后,p(0, 1) 就可以返回 arr[0] 和 arr[1] 中的最大值

p (0, 1) 返回后,p(0, 2) 就会调用 p(2, 2) 去找右边部分的最大值...

依次类推,直到得到 p(0, 5) 的返回值

递归调用过程说明

题外话:有经验的小伙伴可以看出来,这实际就是一个二叉树的后序遍历; 每次把方法压入栈,等到方法执行结束后就出栈, 栈空间大小为树的高度

master 公式

1. 公式说明

用于估计一系列特殊行为的递归时间复杂度,为什么说特殊呢?因为它的使用前提是“分解出的子问题的规模要一样”,我们先来看一下公式

T(N) = a * T (N/b) + O(N^d)

其中 a 表示的是子规模的次数, 像上面那个例子中 a = 2

b 表示的是子问题的规模, 上面例子中 b = 2, 将问题分为了左边最大和右边最大两个子问题

式子最后的 O( ) 表示的是除去调用子过程的其他时间复杂度, 上面例子中为O(1), 因为除去调用子过程,剩下的步骤就是判断相等和取出两者之中的最大值,时间复杂度为常数阶,因此 d = 0

2. 公式求解

那得到 a, b, d 的值有什么用呢?我们可以通过这三个值快速得到递归算法的时间复杂度

序号 条件 时间复杂度
1 logb a < d O(N^d)
2 logb a > d O(N^ (logb a))
3 logb a = d O(N^d * log N)

那通过上述例子的 a = 2, b = 2, d = 0, 可得 logb a = 1 > 0, 为情况 2,时间复杂度为 O(N)

欢迎大家来我博客逛逛 mmimo技术小栈

这篇关于递归过程以及递归master公式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!