Master公式计算递归时间复杂度

我们在算递归算法的时间复杂度时,Master定理为我们提供了很强大的便利!

Master公式在我们的面试编程算法中除了BFPRT算法的复杂度计算不了之外,其他都可以准确计算!

这里用求数组最大值的递归函数来举例:

public static int getMax(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
 
        int mid = (L + R) / 2;
 
        int maxLeft = getMax(arr, L, mid);
        int maxRight = getMax(arr, mid + 1, R);
        return Math.max(maxLeft, maxRight);
    }

master公式:也叫主定理。它提供了一种通过渐近符号表示递推关系式的方法。

                      应用Master定理可以很简便的求解递归方程。

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

①当d<log(b,a)时,时间复杂度为O(n^(logb a))

②当d=log(b,a)时,时间复杂度为O((n^d)*logn)

③当d>log(b,a)时,时间复杂度为O(n^d)
以getMax来说明

将整个数组分为两部分,则左部分为n/2,右部分也为n/2,两者相加,返回操作为O(1)

则得到的式子如下:

T [n] = 2*T[n/2] + O (1)

a=2,b=2,d=0

d<log(b,a)则时间复杂度为O(n)

说明:

递归 就是系统帮自己做 压栈和出栈的过程

分析那个例子:

1 max(arr,0,3) ,开始执行 ,mid=1,然后到 max(arr,0,1)

2 遇到自己的方法max之后,就把当前的状态进行压栈,状态包括 方法调用到第几行,以及过程中的变量,如mid=1,left=0,right=3

3 max(arr,0,1)开始执行,mid=0,然后到max(arr,0,0)

4 遇到自己的方法max之后,就把当前的状态压栈,状态包括 方法调用到第几行,以及过程中的变量,如mid=0,left=0,right=1

5 max(arr,0,0)开始执行,此时left==right,返回值。

6 返回的值如何知道返回给哪个函数呢?此时把 栈顶的信息拿出,还原以前的状态,此时栈顶为max(arr,0,1),运行到

int maxLeft = getMax(arr,L,mid) 这一行,那么返回的值就赋给maxLeft

7 返回之后,函数继续运行,到了int maxRight = getMax(arr,mid+1,R); 此时再把当前的状态压栈,max(arr,0,1) ,行号,maxLeft等

8 同样的方法 把值返回给maxRight,最后返回最大值。如果栈中还有元素,继续出栈,然后赋值,知道最后栈中没有元素。

 

 

 

上一篇:Task11—(困难)树:124


下一篇:给定一个数组,获取其中的最大。最小值