递归与master公式

递归和master公式
master公式：
T(n)=aT(n/b)+o(n^c)
a为递归调用的次数，b为递归分的规模，c为除递归外的时间复杂度
某个递归调用的次数为2，a为2，分成两个大小相等的子问题，b为2，非递归时间复杂度O(1)，c为0，master公式为：
T(n)=2T(n/2)+O(1)；
如果log(b,a) < c: 复杂度为O(n^c)
如果log(b,a) > c: 复杂度为O(n^log(b,a))
如果log(b,a) = c: 复杂度为O(n^c*log n)如果两个子规模不是等规模的，不能用master公式T(N) =  2*T(N/2) + O(n * log n)的时间复杂度为O(n * ((log n)的平方))