Master Therem，翻译成：主定理、主方法、主项定理、大师定理。我个人觉得翻译成大师定理不错，酷酷的。

时间复杂度分析过程

一般情况下

先简单看先O(log(k))，

在二分查找、堆的操作中，一次操作就可以减少一半的工作量，一次循环就少一半，效率不就是 log(k) 嘛。

递归的时间复杂度

问题在于，对于递归求解的时间复杂度分析。

下面的内容转自架构师之路公众号

案例一：计算 1到n的和

时间复杂度分析。

int sum(int n){
    if (n==1) return 1;
	return n+sum(n-1);
}

如何来进行时间复杂度分析呢？

用f(n)来表示数据量为n时，算法的计算次数，很容易知道：

当n=1时，sum函数只计算1次

画外音：if (n==1) return 1;

即：

f(1)=1【式子A】

不难发现，当n不等于1时：

f(n)的计算次数，等于f(n-1)的计算次数，再加1次计算

画外音：return n+sum(n-1);

即：

f(n)=f(n-1)+1【式子B】

【式子B】不断的展开，再配合【式子A】：

画外音：这一句话，是分析这个算法的关键。

f(n)	=f(n-1)+1

f(n-1)	=f(n-2)+1

…

f(2)	=f(1)+1

f(1)	=1

上面共n个等式，左侧和右侧分别相加：

f(n)+f(n-1)+…+f(2)+f(1)

[f(n-1)+1]+[f(n-2)+1]+…+[f(1)+1]+[1]

即得到：

f(n)=n

已经有那么点意思了哈，再来个复杂点的算法。

案例二：二分查找binary_search，

时间复杂度分析。

int BS(int[] arr, int low, int high, int target){

         if (low>high) return -1;

         mid = (low+high)/2;

         if (arr[mid]== target) return mid;

         if (arr[mid]> target)

                  return BS(arr, low, mid-1, target);

         else

                  return BS(arr, mid+1, high, target);

}

二分查找，单纯从递归算法来分析，怎能知道其时间复杂度是O(log(n))呢？

仍用f(n)来表示数据量为n时，算法的计算次数，很容易知道：

当n=1时，bs函数只计算1次

画外音：不用纠结是1次还是1.5次，还是2.7次，是一个常数次。

即：

f(1)=1【式子A】

在n很大时，二分会进行一次比较，然后进行左侧或者右侧的递归，以减少一半的数据量：

f(n)的计算次数，等于f(n/2)的计算次数，再加1次计算

画外音：计算arr[mid]>target，再减少一半数据量迭代

即：

f(n)=f(n/2)+1【式子B】

【式子B】不断的展开，

f(n)	=f(n/2)+1
f(n/2)	=f(n/4)+1
f(n/4)	=f(n/8)+1
…
f(n/2^(m-1))=f(n/2^m)+1

上面共m个等式，左侧和右侧分别相加：

f(n)+f(n/2)+…+f(n/2^(m-1))

[f(n/2)+1]+[f(n/4)+1]+…+[f(n/2^m)]+[1]

即得到：

f(n)=f(n/2^m)+m

再配合【式子A】：

f(1)=1

即，n/2^m=1时, f(n/2^m)=1, 此时m=log(n), 这一步，这是分析这个算法的关键。

将m=log(n)带入，得到：

f(n)=1+log(n)

神奇不神奇？

最后，大boss，快速排序递归算法，时间复杂度的分析过程。

案例三：快速排序quick_sort

时间复杂度分析。

void quick_sort(int[]arr, int low, inthigh){
    if (low==high) return;
    int i = partition(arr, low, high);
    quick_sort(arr, low, i-1);
    quick_sort(arr, i+1, high);
}

仍用f(n)来表示数据量为n时，算法的计算次数，很容易知道：

当n=1时，quick_sort函数只计算1次

f(1)=1【式子A】

在n很大时：

第一步，先做一次partition；

第二步，左半区递归；

第三步，右半区递归；

即：

f(n)=n+f(n/2)+f(n/2)=n+2*f(n/2)【式子B】

画外音：

(1)partition本质是一个for，计算次数是n；

(2)二分查找只需要递归一个半区，而快速排序左半区和右半区都要递归，这一点在分治法与减治法一章节已经详细讲述过；

【式子B】不断的展开，

f(n)	=n+2*f(n/2)
f(n/2)	=n/2+2*f(n/4)
f(n/4)	=n/4+2*f(n/8)
…
f(n/2^(m-1))=n/2^(m-1)+2f(n/2^m)

上面共m个等式，逐步带入，于是得到：

f(n)=n+2*f(n/2)

=n+2*[n/2+2f(n/4)]=2n+4f(n/4)

=2n+4*[n/4+2*f(n/8)]=3n+8f(n/8)

=…

=mn+2^mf(n/2^m)

再配合【式子A】：

f(1)=1

即，$\frac{n}{2^m}=1$时, $f(\frac{n}{2^m})=1$, 此时m=log(n), 这一步，这是分析这个算法的关键。

将m=log(n)带入，得到：

$f(n)=n·log(n)+2^{log(n)}·f(1)=nlog(n)+n$

故，快速排序的时间复杂度是n*log(n)。

wacalei，有点意思哈！

画外音：额，估计83%的同学没有细究看，花5分钟细思上述过程，一定有收获。

总结

for循环的时间复杂度往往是O(n)
树的高度的时间复杂度往往是O(log(n))
二分查找的时间复杂度是O(log(n))，快速排序的时间复杂度n*(log(n))

主定理

内容

设 a>=1 和 b>1 为常数，设f(n)为一函数，T(n)有递归式

$T(n)=a·T(\frac{n}{b})+c·n^d$,则

$$T(n)=\left{\begin{matrix}
O(n^dlog(n) ,if\ a=b^d\
O(n^d),if\ a<b^d\
O(n^{log_ba}),if\ a>b^d)
\end{matrix}\right.$$

详细分析

转自：ghj1222 https://www.cnblogs.com/oier/p/9454539.html

先介绍几个符号的含义。

符号Θ，读音西塔，既是上界也是下界，等于，严格贴紧。

符号O，读音殴，表示上界，小于等于，贴紧未知。

符号o，读音也是殴，小于，不贴紧。

符号Ω，读音偶眯嘎，表示下界，大于等于，贴紧未知。

符号ω，读音也是偶眯嘎，表示下界，大于，不贴紧。

上面的“贴紧”是我根据tight翻译过来的(不是很准确啊)，大概就是是否严格等于的意思吧。

意思就是Θ是平均时间复杂度，O是最坏情况下的复杂度，Ω是最好情况下的复杂度。

假设我们有递推关系式：

$\begin{aligned}T(n)=aT\left(\frac n b\right)+f(n)\end{aligned}$

其中，n为问题的规模、a为递推下子问题的数量，$\frac{n}{b}$为每个子问题的规模，f(n)为递推后做的额外的计算工作。

1.假设存在常数ϵ>0ϵ>0，使得f(n)=O(nlogb(a)−ϵ)f(n)=O(nlogb⁡(a)−ϵ)，则T(n)=Θ(nlogba)T(n)=Θ(nlogba)。

具体意思是f(n)的上界是n的幂次，且logb(a)logb(a)比这个幂次要大，则时间复杂度为这个n的logb(a)logb(a)次。

例子：二叉树的遍历。T(n)=2T(n2)+Θ(1)T(n)=2T(n2)+Θ(1)。其中a=2a=2，b=2b=2，f(n)=1f(n)=1，此时ϵ=1ϵ=1。T(n)=Θ(n)T(n)=Θ(n)。

2.假设存在常数k≥0k≥0，使得f(n)=Θ(nlogbalogkn)f(n)=Θ(nlogb⁡alogk⁡n)，则T(n)=Θ(nlogbalogk+1n)T(n)=Θ(nlogbalogk+1⁡n)。

具体意思是f(n)是n的logb(a)logb(a)次，再乘以一个log，则复杂度是f(n)的复杂度再乘以一个log。

例子：归并排序。T(n)=2T(n2)+Θ(n)T(n)=2T(n2)+Θ(n)。其中a=2a=2，b=2b=2，f(n)=nf(n)=n，此时k=0k=0。T(n)=Θ(nlog2n)T(n)=Θ(nlog2⁡n)。

例子：二分搜索（折半搜索）。T(n)=T(n2)+Θ(1)T(n)=T(n2)+Θ(1)，其中a=1a=1，b=2b=2，f(n)=1f(n)=1，此时k=0k=0，则T(n)=Θ(log2n)T(n)=Θ(log2n)。

3.假设存在常数ϵ>0ϵ>0 ，有f(n)=Ω(nlogb(a)+ϵ)f(n)=Ω(nlogb⁡(a)+ϵ)，同时存在常数c<1c<1以及充分大的nn满足 af(nb)≤cf(n)af(nb)≤cf(n)那么 T(n)=Θ(f(n))T(n)=Θ(f(n))。

这个感觉没啥用啊。。。

【例题】

【NOIP2017初赛】若某算法的计算时间表示为递推关系式：

T(N)=2T(N2)+NlogNT(N)=2T(N2)+Nlog⁡N，T(1)=1T(1)=1，则该算法的时间复杂度为______________________________________________________。

A.O(N) B.O(Nlog2N) C.O(Nlog22N) D.O(N2)A.O(N) B.O(Nlog2⁡N) C.O(Nlog22⁡N) D.O(N2)

【解析】套用情况2中的k=1的情况，则T(n)=Θ(Nlog22N)T(n)=Θ(Nlog22⁡N)，选C

【NOIP2016初赛】若某算法的计算时间表示为递推关系式：

T(N)=2T(N4)+N−−√T(N)=2T(N4)+N，T(1)=1T(1)=1，则该算法的时间复杂度为______________________________________________________。

A.O(N) B.O(N−−√) C.O(N−−√log2N) D.O(N2)A.O(N) B.O(N) C.O(Nlog2⁡N) D.O(N2)

【解析】套用情况2中的k=0的情况，则T(n)=Θ(sqrt(N)log2N)T(n)=Θ(sqrt(N)log2⁡N)，选C

【NOIP2015初赛】某算法的计算时间表示为递推关系式：

T(N)=T(N−1)+NT(N)=T(N−1)+N，T(0)=1T(0)=1。则该算法的时间复杂度为______________________________________________________。

A.O(log22N) B.O(Nlog2N) C.O(N) D.O(N2)A.O(log22⁡N) B.O(Nlog2⁡N) C.O(N) D.O(N2)

【解析】难道这个就要用主定理了？容易推导出T(N)=T(0)+1+…+n=1+N∗(N+1)2T(N)=T(0)+1+…+n=1+N∗(N+1)2，则时间复杂度为O(N2)O(N2)，选D

Adopting CC BY-NC-SA 4.0 License Agreement

MasterTheorem

时间复杂度分析过程

一般情况下

递归的时间复杂度

案例一：计算 1到n的和

案例二：二分查找binary_search，

案例三：快速排序quick_sort

主定理

内容

详细分析

【例题】