算法导论之分治算法算法分析主方法Master Method

在b站看到算法导论的公开课里面讲到了快速分析算法复杂度的主要方法
对于一个递归实现的分治算法，其时间复杂度表示为：

T(n) = aT(n/b)+f(n)
其中，a>=1; b>1; f(n)是不参与递归部分的时间复杂度。a表示分出多少个问题，b体现每个问题规模的大小

比较n^log b (a)与Θ(f(n)) 的大小

switch n^log b (a)与Θ(f(n))的大小
	case >:
	 			复杂度 = Θ(n^logb(a) ) 
	case =:
				复杂度= Θ(f(n)*lgn)
	case <:
				复杂度= Θ(f(n))

例如：T(n) = 2T(n/2)+n ：Θ(n*log(n))（归并排序）