Master公式。（用于计算递归的时间复杂度。）

一、Mster公式

前提条件：

• 递归的子问题的规模必须是相同的。

下面让我来解释一下，这个公式具体的含义。
首先a是一个递归问题的子问题的规模的调用次数，d是子问题的数目，后面的N的d次方就是除了递归子问题的调用，其他问题规模的时间复杂度。

举个例子：

def func(arr, l, r):  # 再arr数组中找到最大的数值
    if l == r:
        return  arr[l]
    mid = l + ((r - l) >> 1)
    l_max = func(arr, l, mid)
    r_max = func(arr, mid + 1, r)
    return max(l_max, r_max)

比如上面的代码就是一个简单的递归。
那么的它的T（N） = 2 * T（N / 2） + O（1）
因为每次调用主函数，需要调用两次规模相同的子问题的函数，所以为2 * T（N / 2），又因为它除了调用子问题的函数，其他的时间复杂度为O（1）.所以这就是这个递归的Master公式。

二、计算时间复杂度

按照这个公式和我们上面的代码，时间复杂度应该为O（N）