1 master 表达式

T(N) = a T(N/b) + O(N^d)

T(N)：整个算法的时间复杂度
a：子过程个数
T(N/b)：子过程的时间复杂度
O(N^d)：出去子过程以外的时间复杂度

若 log(b)a > d，则时间复杂度为 O(N^log(a)b)
若 log(b)a < d，则时间复杂度为 O(N^d)
若 log(b)a = d，则时间复杂度为 O(N^d * logN)
(注意：log(b)a是log以b为底a)

2 举例

log(2)2 = 1
N¹ -> d = 1
log(b)a = N^d
所以时间复杂度为：O(N^d * logN) = O(NlogN)