递归行为时间复杂度计算：master公式

master公式

T(N) = a * T(N/b) + O(N^d)

公式解释

N是初始问题的负责度

a是次数的意思，也就是调用相同规模的递归次数

b是递归的划分，也就是将原问题划分成相同规模的b份

O(N^d)，d是除去递归代码外的其他运算的时间复杂度

例如，二分查找的递归，将原始问题每次划分成两份，依次递归。

这个问题中，每次将问题划分成两份，所以b是2，然后依次递归左右部分，因此，子递归的调用了2次，a是2，除了递归代码，其余部分没有遍历操作，只有简单的O(1)操作，因此，d=0。

所以，master公式为： T(N) = 2 * T(N/2) + O(N^0)

再例如，将上述二分查找，换成每次平均划分三份，那么b=3，依次调用三次，所以a=3，额外时间复杂度仍是O(1)，所以d=0。

所以，master公式为： T(N) = 3 * T(N/3) + O(N^0)

master公式使用

确定了a，b，d后，直接套下列公式

log(b,a) > d ------> 递归时间复杂度为：O(N^log(b,a))

log(b,a) = d ------> 递归时间复杂度为：O(N^d*logN)

log(b,a) < d ------> 递归时间复杂度为：O(N^d)