递归算法每一层函数的时间复杂度的通项形式可以描述如下：
[T(n)=aT(frac{n}{b}) + O(n^d)
]
可以猜测，最后的时间复杂度和这a, b ,d几个参数有关。
整个递归规程的描述用下面一张图就能够概括：
最后的公式是一个累加函数
[Total work = sum^{log_b n}_0 O(n^d)(frac{a}{b^d})^i
]
一看结构，是一个等比数列，公比为(frac{a}{b^d})
接下来就好分析了，等比数列的求和公式为
[S = frac{a_1(1-q^n)}{1-q}
]
后面的分析其实就是针对公比是大于1，等于1，还是小于1做文章。
如果小于1，即
[frac{a}{b^d}< 1Rightarrow log_b a < d
]
看求和公式可知，
[n
ightarrow infty , S = frac{a_1}{1-q} = const
]
常数项忽略，所以结果就是
[Total work = O(n^d)
]
其他两种情况分析类似，这里不再赘述。直接给出结果<font>
参考链接：https://zhuanlan.zhihu.com/p/100531135
