计算时间复杂度的公式

对于T(n) &＃61; a*T(n/b)&＃43;c*n^k;T(1) &＃61; c 这样的递归关系&＃xff0c;有这样的结论&＃xff1a;

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