递归时间复杂度计算公式,时间复杂度计算公式例题

记录：

对于T(n) = aT(n/b)+cn^k;
T(1) = c 这样的递归关系，有这样的结论：

if (a > b^k) T(n) = O(n^(logb(a)));logb(a)b为底a的对数
if (a = b^k) T(n) = O(n^k*logn);
if (a < b^k) T(n) = O(n^k);