master
- master公式是干嘛的呀
master公式是干嘛的呀
master是一个对于递归行为时间复杂度的估算
公式为：T(N) = a * T(N/b) + O(N ^ d);
不用急我们来举一个栗子：
我们先来看看二分法求最大值的代码：
public int maxNum(int[] arr , int l , int r){if(l == r){return arr[l];}mid = l + (r - l) >> 1;int lMax = maxNum(int[] arr , int l , int mid);int rMax = maxNum(int[] arr , int mid + 1 ; int r);return Math.max(lMax , rMax);}
我们先看看master是如何估算上述代码的呢
T(N) = a * T(N/b) + O(N ^ d);
a ： 会有几次调用代码的次数
b ： 每次调用代码的规模大小
O(N ^ d) : 指除了递归行为之外的行为复杂度
所以我们可以得出上述代码二分求最大值位：
T(N) = 2 * T(N/2) + O(1);
- 如果 log（b , a) < d 时间复杂度为： O(N^d)
- 如果log (b , a) > d 时间复杂度为 ： O(N^(log(b,a)))
- 如果log（b , a）== d 时间复杂度为：O(N^d * log(2,n)))
注：log(b,a) 指以b为地a为指数
所以时间复杂度为O(n^log（2,2）) == O(n)