递归行为的时间复杂度估算——master公式

master公式是什么？

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

1. 若log(b, a) > d ，则复杂度为O(N^log(b, a))
2. 若log(b, a) = d ，则复杂度为O(N^d *logN)
3. 若log(b, a) < d ，则复杂度为O(N^d)

master公式使用范围是？

子问题的规模一样

归并排序的时间复杂度如何估算？

由于T(N) = 2T(N/2) + O(N)
所以，a=2, b=2, d=1
所以，时间复杂度为： O(N^1logN) = O(N*logN)