数据结构与算法学习(二)——Master公式及其应用

1. Master公式是什么？

我们在解决算法问题时，经常会用到递归。递归在较难理解的同时，其算法的复杂度也不是很方便计算。而为了较为简便地评估递归的算法复杂度，Master公式应运而生。下面给出Master公式的维基百科链接

1.1 Master公式

$T(N) = a*T(\frac{N}{b}) + O(N^d)$

a：子问题被调用的次数

$\frac{N}{b}$ ：子问题的规模

N：母问题的规模

d：额外操作的次数

当 $log_{b}a < d$ 时， $O(N^d)$ ；

当 $log_{b}a > d$ 时， $O(N^{log_{b}a})$ ；

当 $log_{b}a = d$ 时， $O(N^d*logN)$ ；

2. Master公式的应用举例

使用递归求最大值

代码

public static int maxNum(int[] arr, int L, int R){
    if(L == R) {
        return arr[L];
    }
    int mid = L + ((R - L) >> 1);
    int lMax = maxNum(arr, L, mid);
    int rMax = maxNum(arr, mid + 1, R);
    return Math.max(lMax, rMax);
}

解析：如上是求数组中的最大值的方法，将数组划分成左半部和右半部，求出左边最大值，在求出右边的最大值，最后比较左右的最大值，求出整个数组的最大值。因为将数组划分为左右两部分，所以子问题的规模为 $\frac{N}{2}$ ，即b = 2，又有int lMax = maxNum(arr, L, mid)和int rMax = maxNum(arr, mid + 1, R)的两次调用，所以a = 2，剩下来，有return arr[L]、int mid = L + ((R - L) >> 1)、return Math.max(lMax, rMax)三个常数级的操作，所以d = 0。

将a,b,d代入，则其Master公式可表示为： $T(N) = 2 * T(\frac{N}{2}) + O( 1 )$

根据Master公式， $log_b{a} = log_2{2} = 1 > d = 0$ ，所以，复杂度为 $O(N^{log_ba}) = O(N)$

3. 注意事项

使用Master公式分析递归问题复杂度时，各子问题的规模应该是一致的，否则不能使用Master公式。

本人系菜鸟一枚，所写文章皆为学习总结，大佬请轻喷😱
谢谢阅读😘，欢迎补充！