利用Master公式求递归算法的时间复杂度

Master公式

T(n) = aT(n/b) + O(n^d)

• 参数含义：

Master只适用于子问题规模相同的递归算法
a表示被划分成a个相同规模的子问题
b表示每个子问题处理的数据规模
O(n^d)表示合并子问题解所要花费的时间复杂度

• 复杂度的计算：

①当d<logb a时，时间复杂度为O(n^(logb a))
②当d=logb a时，时间复杂度为O((n^d)*logn)
③当d>logb a时，时间复杂度为O(n^d)