Master Theorem
用途
一种用于计算递归时间复杂度的定理。
比如对于一个时间复杂度递推式：\(T(n)=T(n/2)+O(n)\),
可以浅显地看出它的复杂度为\(O(nlog_2n)\),因为我们这样子的递归写了太多次了。
但我们可以看到\(T(n)=4T(n/2)+n\),
它的复杂度是多少？也是\(O(nlog_2n)\)？
当在问出这种问题时，我们就会有点束手无策。
所以我们就需要一个定理来把这种问题解决。
定理
对于一个时间复杂度递推式的一般式\(T(n)=aT(n/b)+O(n^d)\):
\(T(n)=\begin{cases}
O(n^d) & d>log_b^a \\
O(n^dlog_2^n) & d=log_b^a \\
O(n^{log_b^a}) & d<log_b^a
\end{cases}\)
应用
回到一开始的例子：\(T(n)=4T(n/2)+n\)，
这时\(a=4,b=2,d=1\),
所以\(log_b^a=2>d\)，则\(T(n)=O(n^{log_b^a})=O(n^2)\).
这个故事告诉我们，
像二分这样的形式不要在里面套太大的常数，
不然真的会爆炸。
我们在给出一个例子：\(T(n)=4T(n/2)+n^2\)
这时\(a=4,b=2,d=2\),
所以\(log_b^a=2=d\)，则\(T(n)=O(n^dlog_2^n)=O(n^2log_2^n)\).
还有一种：\(T(n)=4T(n/2)+n^3\)
这时\(a=4,b=2,d=3\),
所以\(log_b^a=2<d\)，则\(T(n)=O(n^d)=O(n^3)\).
总的来说就是谁大跟谁，等大加\(log_2^n\).