-
Master公式是什么？
Master公式用来较为简便地评估递归算法的时间复杂度 -
公式：
T ( N ) = a ∗ T ( N b ) + O ( N d ) T(N) = a*T(\frac{N}{b}) + O(N^d)T(N)=a∗T( bN)+O(N d)
当l o g b a < d log_{b}a < dlog
b
a<d时，时间复杂度为O ( N d ) O(N^d)O(N
d
)；
当l o g b a > d log_{b}a > dlog
b
a>d时，时间复杂度为O ( N l o g b a ) O(N^{log_{b}a})O(N
log
b
a
)；
当l o g b a = d log_{b}a = dlog
b
a=d时，时间复杂度为O ( N d ∗ l o g N ) O(N^d*logN)O(N
d
∗logN)；