算法基础（二）：master公式

简介

在编程中，递归是非常常见的一种算法，由于代码简洁而应用广泛，但递归相比顺序执行或循环程序，时间复杂度难以计算，而master公式就是用于计算递归程序的时间复杂度。

公式

T(N) = aT(N/b) + O(N^d)

• b：子过程的样本量
• a：子过程的计算次数
• O(N^d)：子结果合并的时间复杂度

满足如上公式的程序都可以根据master公式计算时间复杂度：

• log(b，a) > d ：时间复杂度为O(N^log(b，a))
• log(b，a) = d ：时间复杂度为O(N^d * logN)
• log(b，a) < d ：时间复杂度为O(N^d)

示例

计算某个数组最大值

/**
 * @ClassNameDemo
 * @Description 递归
 * @Author lzx
 * @Date2019/10/25 17:32
 * @Version V1.0
 **/
public class Demo {

    //非递归
    private static int getMax(int[] arr) {
        if (arr == null || arr.length < 2) {
            return Integer.MIN_VALUE;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = arr[i] > max ? arr[i] : max;
        }
        return max;
    }

    //递归
    //将数组划分为左右两部分分别计算 则数组最大值即左边最大值和右边最大值中的比较大的值
    private static int getMax2(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        int mid = (left + right) / 2;
        int maxLeft = getMax2(arr, left, mid);
        int maxRight = getMax2(arr, mid + 1, right);
        return Math.max(maxLeft, maxRight);
    }

    public static void main(String[] args) {
        int[] arr = {1, 8, 11, -9, 0, 16, 94, 21};
        System.out.println(getMax(arr));
        System.out.println(getMax2(arr, 0, arr.length - 1));
    }

}

如上递归代码中，将数组分为左右两部分，每部分的计算量为N/2，合并两部分（即比较两部分的最大值）时间复杂度O(1)

则a为2，b为2，d为0，根据master公式，该递归算法的时间复杂度为O(N)