递归和递归时间复杂度

案例一：递归方法求数组最大值

const list = [1, 433, 2, 5, 6, 3, 7]
// 数组l-r间最大值
function getMax(list, l, r) {
  if (l === r) {
    return list[l]
  }
  if (l + 1 === r) {
    return Math.max(list[l], list[r])
  }
  const mid = l + ((r - l) >> 1)
  const leftMax = getMax(list, l, mid)
  const rightMax = getMax(list, mid + 1, r)
  return Math.max(leftMax, rightMax)
}
console.log(getMax(list, 0, list.length - 1))

l到r的中间值求法，一般情况 （l+r）/2，但l+r可能存在溢出，所以优化为 l+（r-l）/2；再优化为 l+（r-l）>>1；

master公式

Master公式，又称为Master定理或主定理，是分析递归算法时间复杂度的一种重要工具，尤其适用于具有分治结构的递归算法。

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

Master公式本身就是递归的形式，是递归方法时间复杂度的一种表示法。T(n) 代表递归方法处理规模为n的数据量的时间复杂度，T(n/b) 代表调用子递归方法的总体时间复杂度，O(n^d) 代表调用子递归方法这行代码外其他代码（下面简称递归外代码）的时间复杂度。

T(n) 是时间复杂度的函数表示法（T=Time）。O(n) 是时间复杂度的表示法，可以理解成一个方法要处理n条数据时，最坏的情况下需要循环执行n次代码所带来的时间成本。

Master公式中的变量

• a: 每次递归调用子问题的数量。即在一个递归方法，需要调用几次子递归方法
• b: 子问题的规模缩小的比例。例如二分法递归搜索时，每次需要查找的数据都缩小了一半，那么 b=2
• d: 每次递归调用之外的代码时间复杂度的参数。例如二分法递归搜索时，每次递归时除了调用递归的方法，没有什么for循环代码，时间复杂度是 O(1)，即 nd=1，因此 d=0

注意：如果一个递归方法每次子问题递归的规模缩小的比例不等，那么无法使用上面的公式。

根据Master公式推导时间复杂度

只要一个递归方法满足Master公式，那么它的时间复杂度就可以确定：

1. 当 d<log(b,a) 时，递归时间复杂度为：O(nlog(b,a))
2. 当 d=log(b,a) 时，递归时间复杂度为：O(n^d * logn)
3. 当 d>log(b,a) 时，递归时间复杂度为：O(n^d)

log(b,a) 指的是以b为底的a的对数，且有 blog(b,a)=a，例如 32=9，则log(3,9)=2。logn 指的是以2为底的n的对数。 这里时间复杂度实际上就是看 d 和 log(b,a) 谁大，取大的那个值为n的指数。如果一样大，任意取一个作为指数，再乘以 logn 即可。这样就好记多了。