说明：

可以用此公式计算调用子程序规模相同的递归的时间复杂度

master公式的使用

Master公式 - 图1

  1. log(b,a) > d ->复杂度为O（N^log(b,a)）
  2. log(b,a) = d ->复杂度为O（N^d*logN）
  3. log(b,a) < d ->复杂度为O（N^d）

    什么意思呢？

a：迭代子算法有几个
b：每个子算法负责多少数据
d：除去子过程剩下的时间复杂度的指数

递归求最大值程序

  1. public class EasyRecurrence {
  2.     //求数组中最大的元素
  3.     public static int getMax(int[] arr, int left, int right) {
  5.         if (left == right) {
  6.             return arr[left];
  7.         }
  9.         int mid = (left + right) / 2;
  10.         int leftMax = getMax(arr, left, mid);
  11.         int rightMax = getMax(arr, mid+1, right);
  12.         return Math.max(leftMax, rightMax);
  13.     }
  15.     public static void main(String[] args) {
  16.         int[] arr = {4,2,1,66,48};
  17.         System.out.println(getMax(arr,0,arr.length-1));
  18.     }
  19. }

首先被求最大值这个问题被分成了两部分，左半部分只求左半部分的最大值，右半部分只求右半部分的最大值，所以a = 2；每个子过程负责多大面积呢？假设总共N个数据的话，left只负责N/2，right也只负责N/2的数据，所以b = 2；除去迭代算法，时间复杂度就是O（1）,也就是N的0次方，所以d = 0；
套master公式：log以b为底a的对数等于log2，也就是1,1是大于d=0的，所以执行第一个，时间复杂度为：O（N^log(2,2)）= O（N）

[

](https://blog.csdn.net/u011679785/article/details/97136820)