主定理(Master Theorem)的通解

我看网上没有相关的推导，于是自己推了一下，算是第一人吧hhhh：

主定理是用来求递归式的时间复杂度常用的方法，然而结论性语言太多了，不符合我们专业的特点。所以，我们很有必要从数学的角度下解释递归式的时间复杂度解法。

给出一个递归式子：

那么可以将它展开成 a 叉树，其高度为⌈logb n⌉（因为每次递归还是分为了 b 份）。

我们可以把这个函数写成一般的级数的形式：

接下来的策略就是，要么将级数积分近似化，要么就直接展开。

其中，积分近似化为：

例子： 求T(n)=2T(n/2)+nlogn 的时间复杂度

因此时间复杂度为O(nlog^2n)